Bumpy pyramid folding
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 p...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
2015
|
| Online Access: | http://hdl.handle.net/1721.1/100406 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-4295-1117 |
| _version_ | 1826189799001686016 |
|---|---|
| author | Abel, Zachary Ryan Demaine, Erik D. Demaine, Martin L. Ito, Hiro Snoeyink, Jack Uehara, Ryuhei |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Abel, Zachary Ryan Demaine, Erik D. Demaine, Martin L. Ito, Hiro Snoeyink, Jack Uehara, Ryuhei |
| author_sort | Abel, Zachary Ryan |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T08:22:26Z |
| format | Article |
| id | mit-1721.1/100406 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:22:26Z |
| publishDate | 2015 |
| record_format | dspace |
| spelling | mit-1721.1/1004062022-09-23T12:33:18Z Bumpy pyramid folding Abel, Zachary Ryan Demaine, Erik D. Demaine, Martin L. Ito, Hiro Snoeyink, Jack Uehara, Ryuhei Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Department of Mathematics Abel, Zachary Ryan Demaine, Erik D. Demaine, Martin L. 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. 2015-12-17T01:55:59Z 2015-12-17T01:55:59Z 2014-08 Article http://purl.org/eprint/type/ConferencePaper http://hdl.handle.net/1721.1/100406 Abel, Zachary R., Erik D. Demaine, Martin L. Demaine, Hiro Ito, Jack Snoeyink, Ryuhei Uehara. "Bumpy pyramid folding." 26th Canadian Conference on Computational Geometry (August 2014). https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-4295-1117 en_US http://www.cccg.ca/proceedings/2014/ Proceedings of the 26th Canadian Conference on Computational Geometry Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Other univ. web domain |
| spellingShingle | Abel, Zachary Ryan Demaine, Erik D. Demaine, Martin L. Ito, Hiro Snoeyink, Jack Uehara, Ryuhei Bumpy pyramid folding |
| title | Bumpy pyramid folding |
| title_full | Bumpy pyramid folding |
| title_fullStr | Bumpy pyramid folding |
| title_full_unstemmed | Bumpy pyramid folding |
| title_short | Bumpy pyramid folding |
| title_sort | bumpy pyramid folding |
| url | http://hdl.handle.net/1721.1/100406 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-4295-1117 |
| work_keys_str_mv | AT abelzacharyryan bumpypyramidfolding AT demaineerikd bumpypyramidfolding AT demainemartinl bumpypyramidfolding AT itohiro bumpypyramidfolding AT snoeyinkjack bumpypyramidfolding AT uehararyuhei bumpypyramidfolding |