Finding the vertices of the sum of two polytopes

T. A. Angelov

Matematičeskaâ fizika i kompʹûternoe modelirovanie, no. 6 (2016), pp. 7-17.

Résumé

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.

Détail

Keywords: polytope, conical hull, Minkowski sum, linear programming.
Mots-clés : vertex

Bibliographie

[1] K. Leichtweiss, Convex Sets, Nauka Publ., M., 1985, 336 pp. | MR

[2] V.\;N. Malozemov, “Modified Simplex Method”, Seminar «DHA CAGD». Izbrannye doklady (20 November 2010), 2010, 1–11 http://dha.spb.ru/reps10.shtml#1120

[3] K. Fukuda, “From the zonotope construction to the Minkowski addition of convex polytopes”, J. Symbolic Comput., 38 (2004), 1261–1272 | DOI | MR | Zbl

[4] P. Gritzmann, B. Sturmfels, “Minkowski addition of polytopes: computational complexity and applications to Grobner bases”, SIAM J. Discrete Math., 6 (1993), 246–269 | DOI | MR | Zbl

[5] F.\;P. Preparata, M.\;I. Shamos, Computational Geometry: An Introduction, Springer, N. Y., 1985, 398 pp. | MR

[6] R. Rockafellar, Convex analysis, Princeton University Press, Princeton, 1970, 470 pp. | MR | Zbl

[7] C. Weibel, Minkowski sums of polytopes, Ph.D. Thesis, EPFL, Lausanne, 2007, 114 pp.