Minkowski Difference

pontryagin_difference(X::LazySet, Y::LazySet)

An alias for the function minkowski_difference.

Notes

There is some inconsistency in the literature regarding the naming conventions. In this library, both the names Minkowski difference and Pontryagin difference refer to the geometric difference of two sets. Mathematically:

\[ X ⊖ Y = \{z ∈ ℝ^n: z + v ∈ X ~∀~v ∈ Y\}\]

minkowski_difference(P::LazySet, Q::LazySet)

Concrete Minkowski difference (geometric difference) of a polytopic set and a compact convex set.

Input

• P – polytopic set
• Q – compact convex set that is subtracted from P

Output

An HPolytope that corresponds to the Minkowski difference of P minus Q if P is bounded, and an HPolyhedron if P is unbounded.

Notes

This implementation requires that the set P is polyhedral and that the set Q is bounded.

Algorithm

This method implements Theorem 2.3 in [1]:

Suppose $P$ is a polyhedron

\[P = \{z ∈ ℝ^n: sᵢᵀz ≤ rᵢ,~i = 1, …, N\}.\]

where $sᵢ ∈ ℝ^n, sᵢ ≠ 0$, and $rᵢ ∈ ℝ$. Assume $ρ(sᵢ,Q)$ is defined for $i = 1, …, N$. Then the Minkowski difference is

\[\{z ∈ ℝ^n: sᵢᵀz ≤ rᵢ - ρ(sᵢ,Q),~i = 1, …, N\}.\]

[1] Ilya Kolmanovsky and Elmer G. Gilbert (1997). Theory and computation of disturbance invariant sets for discrete-time linear systems. Mathematical Problems in Engineering Volume 4, Issue 4, Pages 317-367.

minkowski_difference(Z1::AbstractZonotope, Z2::AbstractZonotope)

Compute the Minkowski difference of two zonotopic sets.

Input

• Z1 – zonotopic set
• Z2 – zonotopic set

Output

An HPolytope that corresponds to the Minkowski difference of Z1 minus Z2.

Algorithm

For one-dimensional sets, we use a simple algorithm for intervals. For two-dimensional sets, this method implements Proposition 6 in [1]. For higher-dimensional sets, this method implements Theorem 3 in [1].

[1] M. Althoff: On computing the Minkowski difference of zonotopes. 2022.

minkowski_difference(H1::AbstractHyperrectangle, H2::AbstractHyperrectangle)

Compute the Minkowski difference of two hyperrectangular sets.

Input

• H1 – hyperrectangular set
• H2 – hyperrectangular set

Output

A Hyperrectangle that corresponds to the Minkowski difference of H1 minus H2, or an EmptySet if the difference is empty.

minkowski_difference(I1::Interval, I2::Interval)

Compute the Minkowski difference of two intervals.

Input

• I1 – interval
• I2 – interval

Output

An Interval that corresponds to the Minkowski difference of I1 minus I2, or an EmptySet if the difference is empty.