Personal tools
You are here: Home Projects Internal Projects Exact Complexity of Minkowski Sums
« August 2017 »
August
SuMoTuWeThFrSa
12345
6789101112
13141516171819
20212223242526
2728293031
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

Abstract

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.

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 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]

Contact

Efi Fogel http://www.cs.tau.ac.il/~efif efif@post.tau.ac.il
Dan Halperin http://acg.cs.tau.ac.il/danhalperin halperin@post.tau.ac.il
Document Actions