Bumpy Pyramid Folding Problem

概要

論文の詳細を見る
Folding problems are investigated for a class of petal (or star-like) polygons P, with an n-polygonal base B surrounded by a sequence of triangles for which adjacent pairs of sides have equal length. Linear time algorithms using constant precision are given 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 bumpy pyramid that is convex. 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 show a polynomial time algorithm that finds the crease pattern to produce the maximum volume bumpy pyramid.
2013-10-30