English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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 shownthat 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 upperbound 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 isknown as the Cayley trick for Minkowski sums. A direct consequence of ourresult 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$, whenthe number of vertices of the polytopes is (asymptotically) the same.

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