Minkowski Sum

minkowski_sum(P::LazySet, Q::LazySet;
              [backend]=nothing, [algorithm]=nothing, [prune]=true)

Compute the Minkowski sum of two polyhedral sets.

Input

• P – set
• Q – set
• backend – (optional, default: nothing) polyhedral computations backend
• algorithm – (optional, default: nothing) algorithm to eliminate variables; available options are Polyhedra.FourierMotzkin, Polyhedra.BlockElimination, and Polyhedra.ProjectGenerators
• prune – (optional, default: true) if true, apply a post-processing to remove redundant constraints or vertices

Output

In two dimensions, if the sets are polygons, the result is a VPolygon. In higher dimensions, the result is an HPolytope if both P and Q are known to be bounded by their types, and an HPolyhedron otherwise.

Notes

This function requires that the list of constraints of both sets P and Q can be obtained. After obtaining the respective lists of constraints, the minkowski_sum method for polyhedral sets is used.

minkowski_sum(P::AbstractPolyhedron, Q::AbstractPolyhedron;
              [backend]=nothing, [algorithm]=nothing, [prune]=true)

Compute the Minkowski sum of two polyhedra in constraint representation.

Input

• P – polyhedron in constraint representation
• Q – polyhedron in constraint representation
• backend – (optional, default: nothing) polyhedral computations backend
• algorithm – (optional, default: nothing) algorithm to eliminate variables; available options are Polyhedra.FourierMotzkin, Polyhedra.BlockElimination, and Polyhedra.ProjectGenerators
• prune – (optional, default: true) if true, apply a post-processing to remove redundant constraints

Output

A polyhedron in H-representation that corresponds to the Minkowski sum of P and Q.

Algorithm

This function implements the concrete Minkowski sum by projection and variable elimination as detailed in [1]. The idea is that if we write $P$ and $Q$ in simple H-representation, that is, $P = \{x ∈ ℝ^n : Ax ≤ b \}$ and $Q = \{x ∈ ℝ^n : Cx ≤ d \}$, then their Minkowski sum can be seen as the projection onto the first $n$-dimensional coordinates of the polyhedron:

\[ \begin{pmatrix} 0 & A \ C & -C \end{pmatrix} \binom{x}{y} ≤ \binom{b}{d}\]

This is seen by noting that $P ⊕ Q$ corresponds to the set of points $x ∈ ℝ^n$ such that $x = y + z$ with $Ay ≤ b$ and $Cz ≤ d$; hence it follows that $Ay ≤ b$ and $C(x-y) ≤ d$, and the inequality above follows by considering the $2n$-dimensional space $\binom{x}{y}$. The reduction from $2n$ to $n$ variables is performed using an elimination algorithm as described next.

The elimination of variables depends on the polyhedra library Polyhedra, which itself uses CDDLib for variable elimination. The available algorithms are:

• Polyhedra.FourierMotzkin – projection by computing the H-representation and applying the Fourier-Motzkin elimination algorithm to it

• Polyhedra.BlockElimination – projection by computing the H-representation and applying the block elimination algorithm to it

• Polyhedra.ProjectGenerators – projection by computing the V-representation

[1] Kvasnica, Michal. "Minkowski addition of convex polytopes." (2005): 1-10.

minkowski_sum(H1::AbstractHyperrectangle, H2::AbstractHyperrectangle)

Concrete Minkowski sum of a pair of hyperrectangular sets.

Input

• H1 – hyperrectangular set
• H2 – hyperrectangular set

Output

A Hyperrectangle corresponding to the Minkowski sum of H1 and H2.

Algorithm

The resulting hyperrectangle is obtained by summing up the centers and radii.

minkowski_sum(Z1::AbstractZonotope, Z2::AbstractZonotope)

Concrete Minkowski sum of a pair of zonotopic sets.

Input

• Z1 – zonotopic set
• Z2 – zonotopic set

Output

A Zonotope corresponding to the Minkowski sum of Z1 and Z2.

Algorithm

The resulting zonotope is obtained by summing up the centers and concatenating the generators of Z1 and Z2.

minkowski_sum(PZ::DensePolynomialZonotope, Z::AbstractZonotope)

Compute the Minkowski sum of a polynomial zonotope and a zonotopic set.

Input

• PZ – polynomial zonotope
• Z – zonotopic set

Output

A polynomial zonotope whose center is the sum of the centers of PZ and Z and whose generators are the concatenation of the generators of PZ and Z.

minkowski_sum(X::AbstractSingleton, Y::AbstractSingleton)

Concrete Minkowski sum of a pair of singletons.

Input

• X – singleton
• Y – singleton

Output

A singleton

Algorithm

The singleton obtained by summing the elements in X and Y.