Embedding Stacked Polytopes on a Polynomial-Size Grid
Lowell Trott, UC Irvine
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(n4) × O(n4) × O(n18).
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.
(Based on a paper by Erik D. Demaine and André Schulz from
SODA 2011.)