2011/01/23 by Erik D. Demaine, André Schulz · 1 citation
Computer Science · Mathematics · Engineering · #Computational Geometry and Mesh Generation #Advanced Combinatorial Mathematics #graph theory and CDMA systems #Polytope #Combinatorics #Convexity #Mathematics #Bounded function #Embedding #Simplex #Facet (psychology) #Integer (computer science) #Discrete mathematics #Computer science #Mathematical analysis
paper · open access · doi:10.1007/s00454-017-9887-6
published in Discrete & Computational Geometry 57(4), 1177-1187 (Springer Science+Business Media)
openalex publication_date 2011/01/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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 2(2d)) , except for one axis, where the coordinates are bounded by O(n3log 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.