# On the Exact Maximum Complexity of Minkowski Sums of Convex Polyhedra

The Minkowski sum M_{11,11} = P_{11} P'_{11}, where P'_{11} is P_{11} rotated 90^{} about the vertical axis. |
|||
---|---|---|---|

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

*m*

_{1},

*m*

_{2},...,

*m*

_{k}facets respectively is bounded from above by ∑

_{1≤i<j≤k}(2

*m*

_{i}− 5)(2

*m*

_{j}− 5) +∑

_{1≤i≤k}

*m*

_{i}+ \binom{

*k*}{2}. Given

*k*positive integers

*m*

_{1},

*m*

_{2},...,

*m*

_{k}, 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

*m*

_{i}− 5)(2

*m*

_{j}− 5) +∑

_{1≤i≤k}

*m*

_{i}+ \binom{

*k*}{2}. When

*k*= 2, for example, the expression above reduces to 4

*m*

_{1}

*m*

_{2}−9m

_{1}−9

*m*

_{2}+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 23*, pages 319-326, Gyeongju, South Korea, 2007 [link] [bibtex]^{rd}ACM Symposium on Computational Geometry (SoCG)

In*Proceedings of the 23*^{rd}European Workshop on Computational Geometry*(EWCG)*, pages 38-41, Graz, 2007 [pdf] [bibtex]

### Contact

Efi Fogel | ||

Dan Halperin |