Loading...
Please wait, while we are loading the content...
Similar Documents
The maximum number of faces of the minkowski sum of three convex polytopes (2012).
| Content Provider | CiteSeerX |
|---|---|
| Author | Karavelas, Menelaos I. Konaxis, Christos Tzanaki, Eleni |
| Abstract | We derive tight expressions for the maximum number of k-faces, 0 ≤ k ≤ d − 1, of the Minkowski sum, P1 + P2 + P3, of three d-dimensional convex polytopes P1, P2 and P3 in R d, as a function of the number of vertices of the polytopes, for any d ≥ 2. Expressing the Minkowski sum as a section of the Cayley polytope C of its summands, counting the k-faces of P1 + P2 + P3 reduces to counting the (k + 2)-faces of 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 R d, where r ≥ d. For d ≥ 4, the maximum values are attained when P1, P2 and P3 are d-polytopes, whose vertex sets are chosen appropriately from three distinct d-dimensional moment-like curves. |
| File Format | |
| Publisher Date | 2012-01-01 |
| Access Restriction | Open |
| Subject Keyword | Minkowski Sum Maximum Number Convex Polytopes P1 P2 P3 Vertex Set Distinct D-dimensional Moment-like Curve D-dimensional Convex Polytopes P1 Tight Bound Tight Expression Cayley Polytope Maximum Value |
| Content Type | Text |
