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(P1::VPolytope, P2::VPolytope;
              [apply_convex_hull]=true,
              [backend]=nothing,
              [solver]=nothing)

Compute the Minkowski sum of two polytopes in vertex representation.

Input

• P1 – polytope
• P2 – polytope
• apply_convex_hull – (optional, default: true) if true, post-process the pairwise sums using a convex-hull algorithm
• backend – (optional, default: nothing) the backend for polyhedral computations used to post-process with a convex hull; see default_polyhedra_backend(P1)
• solver – (optional, default: nothing) the backend used to solve the linear program; see default_lp_solver_polyhedra(N)

Output

A new polytope in vertex representation whose vertices are the convex hull of the sum of all possible sums of vertices of P1 and P2.

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(P::VPolygon, Q::VPolygon)

The Minkowski Sum of two polygons in vertex representation.

Input

• P – polygon in vertex representation
• Q – polygon in vertex representation

Output

A polygon in vertex representation.

Algorithm

We treat each edge of the polygons as a vector, attaching them in polar order (attaching the tail of the next vector to the head of the previous vector). The resulting polygonal chain will be a polygon, which is the Minkowski sum of the given polygons. This algorithm assumes that the vertices of P and Q are sorted in counter-clockwise fashion and has linear complexity $O(m+n)$, where $m$ and $n$ are the number of vertices of P and Q, respectively.

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::Interval, y::Interval)

Concrete Minkowski sum of a pair of intervals.

Input

• x – interval
• y – interval

Output

An Interval corresponding to the Minkowski sum of x and y.

Algorithm

The implementation takes the sum of x and y following the rules of interval arithmetic.

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.

minkowski_sum(P1::SimpleSparsePolynomialZonotope,
              P2::SimpleSparsePolynomialZonotope)

Compute the Minkowski sum of two simple sparse polynomial zonotopes.

Input

• P1 – simple sparse polynomial zonotope
• P2 – simple sparse polynomial zonotope

Output

The Minkowski sum of P1 and P2.

minkowski_sum(P1::SparsePolynomialZonotope, P2::SparsePolynomialZonotope)

Compute the Minkowski sum of two sparse polyomial zonotopes.

Input

• P1 – sparse polynomial zonotope
• P2 – sparse polynomial zonotope

Output

The Minkowski sum of P1 and P2.