On the Exact Maximum Complexity of Minkowski Sums of Convex Polyhedra

We present a tight bound on the exact maximum complexity of Minkowski sums of convex polyhedra in ³. In particular, we prove that the maximum number of facets of the Minkowski sum of two convex polyhedra with m₁,m₂,…,m_k facets respectively is bounded from above by ∑_1≤i<j≤k(2m_i − 5)(2m_j − 5) +∑_1≤i≤k m_i + \binom{k}{2}. Given k positive integers m₁,m₂,…,m_k, we describe how to construct k polytopes with corresponding number of facets respectively, such that the number of facets of their Minkowski sum is exactly ∑_1≤i<j≤k(2m_i − 5)(2m_j − 5) +∑_1≤i≤k m_i + \binom{k}{2}. When k = 2, for example, the expression above reduces to 4m₁m₂ −9m₁ −9m₂ +26. A few pre-constructed polytopes and an interactive program that visualizes them are available at Mink.

The Minkowski sum M11,11 = P11   P’11, where P’11 is P11 rotated 90  about the vertical axis.