Logo der Fakultät Logo LG Theoretische Informatik



Embedding Stacked Polytopes on a Polynomial-Size Grid

AutorInnen: Erik D. Demaine
André Schulz
Kategorie: 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.

Download: arXiv Website
BibTeX-Eintrag: @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 | 04.05.2017
FernUni-Logo FernUniversität in Hagen, LG Theoretische Informatik, 58084 Hagen