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.
