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

preprint2011arXivOpen access

Abstract

We derive tight expressions for the maximum number of kk-faces, 0≤k≤d−10\le{}k\le{}d-1, of the Minkowski sum, P1⊕P2P_1\oplus{}P_2, of two dd-dimensional convex polytopes P1P_1 and P2P_2, as a function of the number of vertices of the polytopes. For even dimensions d≥2d\ge{}2, the maximum values are attained when P1P_1 and P2P_2 are cyclic dd-polytopes with disjoint vertex sets. For odd dimensions d≥3d\ge{}3, the maximum values are attained when P1P_1 and P2P_2 are ⌊d2⌋\lfloor\frac{d}{2}\rfloor-neighborly dd-polytopes, whose vertex sets are chosen appropriately from two distinct dd-dimensional moment-like curves.

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.