http://swrc.ontoware.org/ontology#TechnicalReport
Bumpy Pyramid Folding Problem
en
Department of Mathematics, MIT
Computer Science and Artificial Intelligence Laboratory, MIT
Computer Science and Artificial Intelligence Laboratory, MIT
School of Informatics and Engineering, The University of Electro-Communications
Department of Computer Science, The University of North Carolina
School of Information Science, Japan Advanced Institute of Science and Technology
ZacharyR.Abel
ErikD.Demaine
MartinL.Demaine
Hiro Ito
Jack Snoeyink
Ryuhei Uehara
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.
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.
AN1009593X
研究報告アルゴリズム（AL）
2013-AL-145
19
1-7
2013-10-30