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

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

2011-12-07

arxiv.org/abs/1112.1535v1

Computer Science

Computational Geometry

19 pages

Scientific paper

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_{\substack{1\le{}s_i\le{}n_i s_1+...+s_r=\ell}} \prod_{i=1}^r\binom{n_i}{s_i}$, $\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.

Affiliated with

Also associated with

No associations

Rating

Tight lower bounds on the number of faces of the Minkowski sum of convex polytopes via the Cayley trick does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Tight lower bounds on the number of faces of the Minkowski sum of convex polytopes via the Cayley trick, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tight lower bounds on the number of faces of the Minkowski sum of convex polytopes via the Cayley trick will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-595295