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

Menelaos I. Karavelas and Eleni Tzanaki

Abstract: We derive tight expressions for the maximum values of the 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 if $P_1$ and $P_2$ are cyclic $d$-polytopes with disjoint vertex sets. For odd dimensions $d\ge{}3$, the maximum values are attained if $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.

Guest: Menelaos I. Karavelas
Host: Zvi Lotker

 

Leave a Reply

Your email address will not be published.

163,458 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>