2023-09-27T14:00:21Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmh
oai:ipsj.ixsq.nii.ac.jp:000957442023-04-27T10:00:04Z01164:02592:07086:07297
Bumpy Pyramid Folding ProblemBumpy Pyramid Folding Problemenghttp://id.nii.ac.jp/1001/00095722/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=95744&item_no=1&attribute_id=1&file_no=1Copyright (c) 2013 by the Information Processing Society of JapanDepartment of Mathematics, MITComputer Science and Artificial Intelligence Laboratory, MITComputer Science and Artificial Intelligence Laboratory, MITSchool of Informatics and Engineering, The University of Electro-CommunicationsDepartment of Computer Science, The University of North CarolinaSchool of Information Science, Japan Advanced Institute of Science and TechnologyZacharyR.AbelErikD.DemaineMartinL.DemaineHiro, ItoJack, SnoeyinkRyuhei, UeharaFolding 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-14519172013-10-302013-10-22