Veröffentlichung

Titel:

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

Abstract:

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

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} }