CGAL homepage   ACG at TAU  
TAU Members   People   Projects  

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 Y axis.
[dual] [primal] [dual]
PrimalDualDual

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 m and n facets respectively is bounded from above by f(m,n) = 4mn - 9m - 9n + 26. Given two positive integers m and n, we describe how to construct two convex polyhedra with m and n facets respectively, such that the number of facets of their Minkowski sum is exactly f(m,n). We generalize the construction to yield a lower bound on the maximum complexity of Minkowski sums of many convex polyhedra in 3. That is, given k positive integers m1,m2,...,mk, we describe how to construct k convex polyhedra with corresponding number of facets, such that the number of facets of their Minkowski sum is exactly 1 i < j k(2mi - 5)(2mj - 5) + \binom{k}{2} + 1 i kmi. We also provide a conservative upper bound for the general case. A few pre-constructed convex polyhedra and an interactive program that visualizes them are available at Mink.

Links

Contact

Efi Fogel http://www.cs.tau.ac.il/~efif efif@post.tau.ac.il

[Projects Page] [Top]
Site is maintained by Efi Fogel. Last modified: August 19 2007.