Mathematics

Finding the vertices of the sum of two polytopes

T. A. Angelov

Saint Petersburg State University

Abstract: This work introduces a criterion for finding the vertices of a Minkowski sum of two polytopes $\mathrm{conv} A \subset \mathbb{R}^n$ and $\mathrm{conv} B \subset \mathbb{R}^n$, where $A = \{ a_0, \dots , a_m \}$ and $B = \{ b_0, b_1, \dots, b_{m_b}\}$. These convex sets are also denoted as V-polytopes. The constructions used in the present paper stay entirely in the space of V-polytopes, without any transitions to their duals, that is H-polytopes (half-space representation).
Before formulating a general criterion, we consider a special case—the sum of a polytope $\mathrm{conv} A$ and a line segment $\mathrm{conv}\{b_0, b_1\}$.
The following lemma holds. Fix $i$ in $0:m$.
1) If $v \not \in K(a_i)$, then $a_i + v$ is a vertex of $\mathrm{conv} A_v$.
    Else, $a_i + v$ is not a vertex of $\mathrm{conv} A_v$.
2) If $-v \not \in K(a_i)$, then $a_i$ is a vertex of $\mathrm{conv} A_v$.
    Else, $a_i$ is not a vertex of $\mathrm{conv} A_v$.
Here $A_v = \{ a_0, a_1, \dots , a_m, a_0 + v, a_1 + v, \dots , a_m + v\}$, $v = b_1 - b_0$,
$$ K(a_i) := K( \mathrm{conv} \left\{ a_0 - a_i, a_1 - a_i, \dots, a_{i-1} - a_i, a_{i+1} - a_i, \dots, a_m - a_i \right\}), $$
where $K(C)$ is a cone generated by set $C$.
Using an analogical scheme of reasoning as in the lemma, we present the main result of the this work.
Theorem. Fix $i \in 0:m$ and $j \in 0:m_b$. The point $a_i + b_j$ is a vertex of the polytope $\mathrm{conv} A + \mathrm{conv}B$ if and only if cones $K(b_j)$ and $K(a_i)$ do not intersect.
The suggested criterion possesses an intuitive graphic interpretation and is proven by elementary tools of convex anaylsis. In conclusion we note, that the theorem can be applied solving a linear programming problem. Moreover, the latter turns out to be dual to a similar LP problem, constructed using the properties of H-polytopes.

Keywords: polytope, conical hull, Minkowski sum, vertex, linear programming.

UDC: 519.852.2
BBK: 22.135

DOI: 10.15688/jvolsu1.2016.6.1