On the Exact Maximum Complexity of Minkowski Sums of Convex Polyhedra

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

Abstract

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.

Links

• Efi Fogel, and Dan Halperin, and Christophe Weibel
  On the Exact Maximum Complexity of Minkowski Sums of Convex Polyhedra
  Journal of Discrete and Computational Geometry, Springer New York, 42(4): 654-669, 2009 [link] [bibtex]
  In Proceedings of the 23^rd ACM Symposium on Computational Geometry (SoCG), pages 319-326, Gyeongju, South Korea, 2007 [link] [bibtex]
  In Proceedings of the 23^rd European Workshop on Computational Geometry (EWCG), pages 38-41, Graz, 2007 [pdf] [bibtex]

Contact

Efi Fogel
Dan Halperin