Embedding Stacked Polytopes on a Polynomial-Size Grid
Erik D. Demaine
André Schulz
Artikel in Zeitschriften
erschienen in:
Discrete & Computational Geometry, Vol. 57, Nr. 4, 2017, pp. 782-809

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(n2log(2d)), except for one axis, where the coordinates are bounded by O(n3log(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.

@article{DBLP:journals/dcg/DemaineS17, author = {Erik D. Demaine and Andr{\'{e}} Schulz}, title = {Embedding Stacked Polytopes on a Polynomial-Size Grid}, journal = {Discrete {\&} Computational Geometry}, volume = {57}, number = {4}, pages = {782--809}, year = {2017} }
Christoph Doppelbauer | 10.05.2024