Finding the vertices of the sum of two polytopes

This work introduces a criterion for finding the vertices of a Minkowski sum of two polytopes conv𝐴 ⊂ R𝑛 and conv𝐵 ⊂ R𝑛, where = = {𝑎0,..., 𝑎𝑚} and = {𝑏0, 𝑏1,..., 𝑏𝑚𝑏}. 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 conv𝐴 and a line segment conv{𝑏0, 𝑏1}. The following lemma holds. Fix in 0 : 𝑚. 1) If 𝑣 ̸∈ 𝐾(𝑎𝑖), then + is a vertex of conv𝐴𝑣. Else, + is not a vertex of conv𝐴𝑣. 2) If -𝑣 ̸∈ 𝐾(𝑎𝑖), then is a vertex of conv𝐴𝑣. Else, is not a vertex of conv𝐴𝑣. Here = {𝑎0, 𝑎1,..., 𝑎𝑚, 𝑎0 + 𝑣, 𝑎1 + 𝑣,..., + 𝑣}, = 𝑏1 - 𝑏0, 𝐾(𝑎𝑖) := 𝐾(conv {𝑎0 - 𝑎𝑖, 𝑎1 - 𝑎𝑖,..., 𝑎𝑖-1 - 𝑎𝑖, 𝑎𝑖+1 - 𝑎𝑖,..., - 𝑎𝑖}), where 𝐾(𝐶) is a cone generated by set 𝐶. Using an analogical scheme of reasoning as in the lemma, we present the main result of the this work. Theorem. Fix ∈ 0 : and ∈ 0 : 𝑚𝑏. The point + is a vertex of the polytope conv𝐴 + conv𝐵 if and only if cones -𝐾(𝑏𝑗) and 𝐾(𝑎𝑖) 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.