Diameter, decomposability, and Minkowski sums of polytopes
Abstract
We investigate how the Minkowski sum of two polytopes affects their graph
and, in particular, their diameter. We show that the diameter of the Minkowski
sum is bounded below by the diameter of each summand and above by, roughly, the
product between the diameter of one summand and the number of vertices of the
other. We also prove that both bounds are sharp. In addition, we obtain a
result on polytope decomposability. More precisely, given two polytopes P and
Q, we show that P can be written as a Minkowski sum with a summand homothetic
to Q if and only if P has the same number of vertices as its Minkowski sum with
Q.