Personal tools
You are here: Home Projects In-house Projects Exact Complexity of Minkowski Sums
« February 2023 »
Log in

Forgot your password?

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.
[dual] [primal] [dual]
Primal Dual Dual


We present a tight bound on the exact maximum complexity of Minkowski sums of convex polyhedra in 3. In particular, we prove that the maximum number of facets of the Minkowski sum of two convex polyhedra with m1,m2,...,mk facets respectively is bounded from above by ∑1≤i<jk(2mi − 5)(2mj − 5) +∑1≤i≤k mi + \binom{k}{2}. Given k positive integers m1,m2,...,mk, 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<jk(2mi − 5)(2mj − 5) +∑1≤i≤k mi + \binom{k}{2}. When k = 2, for example, the expression above reduces to 4m1m2 −9m1 −9m2 +26. A few pre-constructed polytopes and an interactive program that visualizes them are available at Mink.


  • 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 23rd ACM Symposium on Computational Geometry (SoCG), pages 319-326, Gyeongju, South Korea, 2007 [link] [bibtex]
    In Proceedings of the 23rd European Workshop on Computational Geometry (EWCG), pages 38-41, Graz, 2007 [pdf] [bibtex]


Efi Fogel
Dan Halperin
Document Actions