The question if every polyhedral graph can be embedded as a convex polyhedron on a polynomially sized 3d grid is one of the main open problems in lower dimensional polytope theory. Currently, the best known algorithm requires a grid of size O(2~(7.21n)), for n being the number of the vertices. We show that prismatoids (polytopes, whose graphs are coming from triangulated polygonal annuli) can be embedded as convex polyhedra on a grid of size O(n~4) × O(n~3) ×1.
展开▼
