The Minkowski sum M11,11 = P11 P'11, where P'11 is P11 rotated 90 about the vertical axis. |
![[dual]](ngm_mink_11_11_primal.gif) |
![[primal]](ngm_mink_11_11_dual.gif) |
![[dual]](ngm_mink_11_11_dual_bottom.gif) |
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<j≤k(2
mi − 5)(2
mj − 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<j≤k(2
mi − 5)(2
mj − 5) +∑
1≤i≤k mi + \binom{
k}{2}. When
k = 2, for
example, the expression above reduces to 4
m1m2 −9m
1 −9
m2 +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