Fall 2014: Theory Seminar
Donald Bren Hall, Room 1425, 1:00pm
November 14, 2014:

Bumpy Pyramid Folding

Zachary Becker

We investigate folding problems for a class of petal polygons $P$, which have an $n$-polygonal base $B$ surrounded by a sequence of triangles. We give linear time algorithms using constant precision to determine if $P$ can fold to a pyramid with flat base $B$, and to determine a triangulation of $B$ (crease pattern) that allows folding into a convex (triangulated) polyhedron. By Alexandrov's theorem, the crease pattern is unique if it exists, but the general algorithm known for this theorem is pseudo-polynomial, with very large running time; ours is the first efficient algorithm for Alexandrov's theorem for a special class of polyhedra. We also give a polynomial time algorithm that finds the crease pattern to produce the maximum volume triangulated polyhedron.

(Based on a paper from CCCG 2014 by Zachary R. Abel, Erik D. Demaine, Martin L. Demaine, Hiro Ito, Jack Snoeyink, and Ryuhei Uehara.)