Bumpy Pyramid Folding Problem

• Item type: SIG Technical Reports(1)
• 公開日: 2013-10-30
• タイトル: Bumpy Pyramid Folding Problem
• タイトル / 言語: en
• タイトル: Bumpy Pyramid Folding Problem
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 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
• 著者所属(英): en
• 著者所属(英): Department of Mathematics, MIT
• 著者所属(英): en
• 著者所属(英): Computer Science and Artificial Intelligence Laboratory, MIT
• 著者所属(英): en
• 著者所属(英): Computer Science and Artificial Intelligence Laboratory, MIT
• 著者所属(英): en
• 著者所属(英): School of Informatics and Engineering, The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, The University of North Carolina
• 著者所属(英): en
• 著者所属(英): School of Information Science, Japan Advanced Institute of Science and Technology
• 著者名: ZacharyR.Abel; ErikD.Demaine; MartinL.Demaine; Hiro, Ito; Jack, Snoeyink; Ryuhei, Uehara
• 著者名(英): Zachary, R.Abel; Erik, D.Demaine; Martin, L.Demaine; Hiro, Ito; Jack, Snoeyink; Ryuhei, Uehara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2013-AL-145, 号 19, p. 1-7, 発行日 2013-10-30
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会