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

preprint2012arXivOpen 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+P2+P3P_1+P_2+P_3, of three dd-dimensional convex polytopes P1P_1, P2P_2 and P3P_3, as a function of the number of vertices of the polytopes, for any d≥2d\ge 2. Expressing the Minkowski sum of the three polytopes as a section of their Cayley polytope C\mathcal{C}, the problem of counting the number of kk-faces of P1+P2+P3P_1+P_2+P_3, reduces to counting the number of (k+2)(k+2)-faces of the subset of C\mathcal{C} comprising of the faces that contain at least one vertex from each PiP_i. In two dimensions our expressions reduce to known results, while in three dimensions, the tightness of our bounds follows by exploiting known tight bounds for the number of faces of rr dd-polytopes, where r≥dr\ge d. For d≥4d\ge 4, the maximum values are attained when P1P_1, P2P_2 and P3P_3 are dd-polytopes, whose vertex sets are chosen appropriately from three 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.