Minkowski Difference

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.