## 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.)