Abstract | ||
---|---|---|
We derive tight expressions for the maximum number of k-faces, 0 <= k <= 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 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 P-1 + P-2 + P-3 reduces to counting the (k + 2)- faces of C that contain vertices from each 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 P-1, P-2 and P-3 are d-polytopes, whose vertex sets are chosen appropriately from three distinct d-dimensional moment-like curves. |
Year | DOI | Venue |
---|---|---|
2015 | 10.20382/jocg.v6i1a2 | JOURNAL OF COMPUTATIONAL GEOMETRY |
Keywords | Field | DocType |
discrete geometry,combinatorial geometry,minkowski sum | Topology,Discrete mathematics,Combinatorics,Vertex (geometry),Regular polygon,Polytope,Minkowski addition,Mathematics | Journal |
Volume | Issue | ISSN |
6 | 1 | 1920-180X |
Citations | PageRank | References |
5 | 0.50 | 12 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Menelaos I. Karavelas | 1 | 229 | 18.99 |
Christos Konaxis | 2 | 63 | 6.99 |
Eleni Tzanaki | 3 | 24 | 6.72 |