Loading...
Please wait, while we are loading the content...
Similar Documents
The maximum number of faces of the Minkowski sum of three convex polytopes
| Content Provider | arXiv |
|---|---|
| Author | Karavelas, Menelaos I. Konaxis, Christos Tzanaki, Eleni |
| Date of Submission | 2012-11-26 |
| 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$, as a function of the number of vertices of the polytopes, for any $d\ge 2$. Expressing the Minkowski sum of the three polytopes as a section of their Cayley polytope $\mathcal{C}$, the problem of counting the number of $k$-faces of $P_1+P_2+P_3$, reduces to counting the number of $(k+2)$-faces of the subset of $\mathcal{C}$ comprising of the faces that contain at least one vertex from each $P_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 $r$ $d$-polytopes, 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. |
| Related Links | https://arxiv.org/pdf/1211.6089.pdf |
| Page Count | 44 |
| arXiv | 1211.6089 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Computer Science - Computational Geometry Mathematics - Combinatorics Nonnumerical Algorithms and Problems Computer Science Mathematics Combinatorial complexity of geometric structures $n$-dimensional polytopes Combinatorial properties (number of faces, shortest paths, etc.) Computer graphics; computational geometry |
| Content Type | Text |
| Resource Type | Article |
| Subject | Mathematics |
