Tight lower bounds on the number of faces of the Minkowski sum of convex polytopes via the Cayley trick

Abstract

Consider a set of $r$ convex $d$-polytopes $P_1,P_2,...,P_r$, where $d\ge 3$ and $r\ge 2$, and let $n_i$ be the number of vertices of $P_i$, $1\le i\le r$. It has been shown by Fukuda and Weibel that the number of $k$-faces of the Minkowski sum, $P_1+P_2+...+P_r$, is bounded from above by ${\Phi }_{k+r}(n_1,n_2,...,n_r)$, where ${\Phi }_{\ell }(n_1,n_2,...,n_r)={\sum }_{\begin{array}{c}1\le s_i\le n_i{s}_1+...+s_r=\ell \end{array}}{\prod }_{i=1}^r\left(\genfrac{}{}{0ex}{}{n_i}{s_i}\right)$, $\ell \ge r$. Fukuda and Weibel have also shown that the upper bound mentioned above is tight for $d\ge 4$, $2\le r\le \lfloor \frac{d}{2}\rfloor$, and for all $0\le k\le \lfloor \frac{d}{2}\rfloor -r$. In this paper we construct a set of $r$ neighborly $d$-polytopes $P_1,P_2,...,P_r$, where $d\ge 3$ and $2\le r\le d-1$, for which the upper bound of Fukuda and Weibel is attained for all $0\le k\le \lfloor \frac{d+r-1}{2}\rfloor -r$. Our approach is based on what is known as the Cayley trick for Minkowski sums. A direct consequence of our result is a tight asymptotic bound on the complexity of the Minkowski sum $P_1+P_2+...+P_r$, for any fixed dimension $d$ and any $2\le r\le d-1$, when the number of vertices of the polytopes is (asymptotically) the same.

19 pages

References in corpus (3)

• On f-vectors of Minkowski additions of convex polytopes
• Topological obstructions for vertex numbers of Minkowski sums
• Minkowski Sum Construction and other Applications of Arrangements of Geodesic Arcs on the Sphere