Embedding Stacked Polytopes on a Polynomial-Size Grid
A stacking operation adds a d-simplex on top of a facet of a simplicial d-polytope while maintaining the convexity of the polytope. A stacked d-polytope is a polytope that is obtained from a d-simplex and a series of stacking operations. We show that for a fixed d every stacked d-polytope with n ver...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2017
|
| Online Access: | http://hdl.handle.net/1721.1/108786 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1811082645080113152 |
|---|---|
| author | Schulz, André Demaine, Erik D |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Schulz, André Demaine, Erik D |
| author_sort | Schulz, André |
| collection | MIT |
| description | A stacking operation adds a d-simplex on top of a facet of a simplicial d-polytope while maintaining the convexity of the polytope. A stacked d-polytope is a polytope that is obtained from a d-simplex and a series of stacking operations. We show that for a fixed d every stacked d-polytope with n vertices can be realized with nonnegative integer coordinates. The coordinates are bounded by O(n[superscript 2 log[subscript 2](2d)], except for one axis, where the coordinates are bounded by O(n[superscript 3 log[subscript 2](2d)]. The described realization can be computed with an easy algorithm. The realization of the polytopes is obtained with a lifting technique which produces an embedding on a large grid. We establish a rounding scheme that places the vertices on a sparser grid, while maintaining the convexity of the embedding. |
| first_indexed | 2024-09-23T12:06:41Z |
| format | Article |
| id | mit-1721.1/108786 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:06:41Z |
| publishDate | 2017 |
| publisher | Springer US |
| record_format | dspace |
| spelling | mit-1721.1/1087862022-10-01T08:16:31Z Embedding Stacked Polytopes on a Polynomial-Size Grid Schulz, André Demaine, Erik D Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D A stacking operation adds a d-simplex on top of a facet of a simplicial d-polytope while maintaining the convexity of the polytope. A stacked d-polytope is a polytope that is obtained from a d-simplex and a series of stacking operations. We show that for a fixed d every stacked d-polytope with n vertices can be realized with nonnegative integer coordinates. The coordinates are bounded by O(n[superscript 2 log[subscript 2](2d)], except for one axis, where the coordinates are bounded by O(n[superscript 3 log[subscript 2](2d)]. The described realization can be computed with an easy algorithm. The realization of the polytopes is obtained with a lifting technique which produces an embedding on a large grid. We establish a rounding scheme that places the vertices on a sparser grid, while maintaining the convexity of the embedding. 2017-05-09T18:45:59Z 2018-01-07T06:00:05Z 2017-03 2017-04-25T03:46:25Z Article http://purl.org/eprint/type/JournalArticle 0179-5376 1432-0444 http://hdl.handle.net/1721.1/108786 Demaine, Erik D., and André Schulz. “Embedding Stacked Polytopes on a Polynomial-Size Grid.” Discrete & Computational Geometry 57, no. 4 (March 21, 2017): 782–809. https://orcid.org/0000-0003-3803-5703 en http://dx.doi.org/10.1007/s00454-017-9887-6 Discrete & Computational Geometry Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ Springer Science+Business Media New York application/pdf Springer US Springer US |
| spellingShingle | Schulz, André Demaine, Erik D Embedding Stacked Polytopes on a Polynomial-Size Grid |
| title | Embedding Stacked Polytopes on a Polynomial-Size Grid |
| title_full | Embedding Stacked Polytopes on a Polynomial-Size Grid |
| title_fullStr | Embedding Stacked Polytopes on a Polynomial-Size Grid |
| title_full_unstemmed | Embedding Stacked Polytopes on a Polynomial-Size Grid |
| title_short | Embedding Stacked Polytopes on a Polynomial-Size Grid |
| title_sort | embedding stacked polytopes on a polynomial size grid |
| url | http://hdl.handle.net/1721.1/108786 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT schulzandre embeddingstackedpolytopesonapolynomialsizegrid AT demaineerikd embeddingstackedpolytopesonapolynomialsizegrid |