Paper by Erik D. Demaine

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⁴) × O(n⁴) × O(n¹⁸). 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)