On the exact maximum complexity of Minkowski sums of convex polyhedra
Efi Fogel, Dan Halperin, Christophe Weibel · 2007
We present a tight bound on the exact maximum complexity of Minkowski sums of convex polyhedra in R 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 R 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 P 1≤i