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

preprint2011arXivOpen access

Abstract

Consider a set of rr convex dd-polytopes P1,P2,...,PrP_1,P_2,...,P_r, where d≥3d\ge{}3 and r≥2r\ge{}2, and let nin_i be the number of vertices of PiP_i, 1≤i≤r1\le{}i\le{}r. It has been shown by Fukuda and Weibel that the number of kk-faces of the Minkowski sum, P1+P2+...+PrP_1+P_2+...+P_r, is bounded from above by Φk+r(n1,n2,...,nr)Φ_{k+r}(n_1,n_2,...,n_r), where Φℓ(n1,n2,...,nr)=∑1≤si≤nis1+...+sr=ℓ∏i=1r(nisi)Φ_{\ell}(n_1,n_2,...,n_r)= \sum_{\substack{1\le{}s_i\le{}n_i s_1+...+s_r=\ell}} \prod_{i=1}^r\binom{n_i}{s_i}, ℓ≥r\ell\ge{}r. Fukuda and Weibel have also shown that the upper bound mentioned above is tight for d≥4d\ge{}4, 2≤r≤⌊d2⌋2\le{}r\le{}\lfloor\frac{d}{2}\rfloor, and for all 0≤k≤⌊d2⌋−r0\le{}k\le{}\lfloor\frac{d}{2}\rfloor-r. In this paper we construct a set of rr neighborly dd-polytopes P1,P2,...,PrP_1,P_2,...,P_r, where d≥3d\ge{}3 and 2≤r≤d−12\le{}r\le{}d-1, for which the upper bound of Fukuda and Weibel is attained for all 0≤k≤⌊d+r−12⌋−r0\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 P1+P2+...+PrP_1+P_2+...+P_r, for any fixed dimension dd and any 2≤r≤d−12\le{}r\le{}d-1, when the number of vertices of the polytopes is (asymptotically) the same.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.