The maximum number of faces of the Minkowski sum of two convex polytopes

Abstract

We derive tight expressions for the maximum number of $k$-faces, $0\le k\le d-1$, of the Minkowski sum, $P_1\oplus P_2$, of two $d$-dimensional convex polytopes $P_1$ and $P_2$, as a function of the number of vertices of the polytopes. For even dimensions $d\ge 2$, the maximum values are attained when $P_1$ and $P_2$ are cyclic $d$-polytopes with disjoint vertex sets. For odd dimensions $d\ge 3$, the maximum values are attained when $P_1$ and $P_2$ are $\lfloor \frac{d}{2}\rfloor$-neighborly $d$-polytopes, whose vertex sets are chosen appropriately from two distinct $d$-dimensional moment-like curves.

arXiv comment37 pages, 8 figures, conference version to appear at SODA 2012; v2: fixed typos, made stylistic changes, added figures