**Reference**:- Erik D. Demaine and André Schulz, “Embedding Stacked Polytopes on a Polynomial-Size Grid”, in
*Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)*, San Francisco, California, USA, January 22–25, 2011, pages 1177–1187. **Abstract**:-
We show how to realize a stacked 3D polytope
(formed by repeatedly stacking a tetrahedron onto a triangular face)
by a strictly convex embedding with its
*n*vertices on an integer grid of size*O*(*n*^{4}) ×*O*(*n*^{4}) ×*O*(*n*^{18}). We use a perturbation technique to construct an integral 2D embedding that lifts to a small 3D polytope, all in linear time. This result solves a question posed by Günter M. Ziegler, and is the first nontrivial subexponential upper bound on the long-standing open question of the grid size necessary to embed arbitrary convex polyhedra, that is, about efficient versions of Steinitz's 1916 theorem. An immediate consequence of our result is that*O*(log*n*)-bit coordinates suffice for a greedy routing strategy in planar 3-trees. **Comments**:- This paper is also available from SIAM.
**Length**:- The paper is 11 pages.
**Availability**:- The paper is available in PDF (425k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- StackedPolytopes_DCG (Embedding Stacked Polytopes on a Polynomial-Size Grid)

See also other papers by Erik Demaine.

Last updated April 22, 2019 by Erik Demaine.