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

Karavelas, Menelaos I. and Konaxis, Christos and Tzanaki, Eleni (2012) The maximum number of faces of the Minkowski sum of three convex polytopes. In Proc. of the 29th ACM Symposium on Computational Geometry (SoCG 2013), June 17-20, 2013 - Rio de Janeiro, Brazil.. (In Press)

[img] Text
acmac-0191.pdf

Download (515Kb)

Abstract

We derive tight expressions for the maximum number of $k$-faces, $0\le{}k\le{}d-1$, of the Minkowski sum, $P_1+P_2+P_3$, of three $d$-dimensional convex polytopes $P_1$, $P_2$ and $P_3$ in $\reals^d$, as a function of the number of vertices of the polytopes, for any $d\ge{}2$. Expressing the Minkowski sum as a section of the Cayley polytope $\mathcal{C}$ of its summands, counting the $k$-faces of $P_1+P_2+P_3$ reduces to counting the $(k+2)$-faces of $\mathcal{C}$ which meet the vertex sets of the three polytopes. 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 $r$ $d$-polytopes in $\reals^d$, where $r\ge d$. For $d\ge{}4$, the maximum values are attained when $P_1$, $P_2$ and $P_3$ are $d$-polytopes, whose vertex sets are chosen appropriately from three distinct $d$-dimensional moment-like curves.

Item Type: Article
Depositing User: Christos Konaxis
Date Deposited: 19 Mar 2013 08:30
Last Modified: 05 May 2017 13:48
URI: http://preprints.acmac.uoc.gr/id/eprint/191

Actions (login required)

View Item View Item