pith. sign in

arxiv: 1106.6254 · v2 · pith:NIP74E57new · submitted 2011-06-30 · 💻 cs.CG · math.CO

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

classification 💻 cs.CG math.CO
keywords polytopesmaximumnumberattainedconvexdimensionaldimensionsfaces
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.