Algorithms for Designing Pop-Up Cards
We prove that every simple polygon can be made as a (2D) pop-up card/book that opens to any desired angle between 0 and 360°. More precisely, given a simple polygon attached to the two walls of the open pop-up, our polynomial-time algorithm subdivides the polygon into a single-degree-of-freedom link...
| Main Authors: | , , , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Schloss Dagstuhl Publishing
2014
|
| Online Access: | http://hdl.handle.net/1721.1/87552 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-4295-1117 https://orcid.org/0000-0002-3182-1675 |
| _version_ | 1826193705684434944 |
|---|---|
| author | Abel, Zachary Ryan Demaine, Erik D. Demaine, Martin L. Eisenstat, Sarah Charmian Lubiw, Anna Schulz, Andre Souvaine, Diane L. Viglietta, Giovanni Winslow, Andrew |
| 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. Eisenstat, Sarah Charmian Lubiw, Anna Schulz, Andre Souvaine, Diane L. Viglietta, Giovanni Winslow, Andrew |
| author_sort | Abel, Zachary Ryan |
| collection | MIT |
| description | We prove that every simple polygon can be made as a (2D) pop-up card/book that opens to any desired angle between 0 and 360°. More precisely, given a simple polygon attached to the two walls of the open pop-up, our polynomial-time algorithm subdivides the polygon into a single-degree-of-freedom linkage structure, such that closing the pop-up flattens the linkage without collision. This result solves an open problem of Hara and Sugihara from 2009. We also show how to obtain a more efficient construction for the special case of orthogonal polygons, and how to make 3D orthogonal polyhedra, from pop-ups that open to 90°, 180°, 270°, or 360°. |
| first_indexed | 2024-09-23T09:43:22Z |
| format | Article |
| id | mit-1721.1/87552 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:43:22Z |
| publishDate | 2014 |
| publisher | Schloss Dagstuhl Publishing |
| record_format | dspace |
| spelling | mit-1721.1/875522022-09-26T13:21:46Z Algorithms for Designing Pop-Up Cards Abel, Zachary Ryan Demaine, Erik D. Demaine, Martin L. Eisenstat, Sarah Charmian Lubiw, Anna Schulz, Andre Souvaine, Diane L. Viglietta, Giovanni Winslow, Andrew Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Mathematics Abel, Zachary Ryan Demaine, Erik D. Demaine, Martin L. Eisenstat, Sarah Charmian We prove that every simple polygon can be made as a (2D) pop-up card/book that opens to any desired angle between 0 and 360°. More precisely, given a simple polygon attached to the two walls of the open pop-up, our polynomial-time algorithm subdivides the polygon into a single-degree-of-freedom linkage structure, such that closing the pop-up flattens the linkage without collision. This result solves an open problem of Hara and Sugihara from 2009. We also show how to obtain a more efficient construction for the special case of orthogonal polygons, and how to make 3D orthogonal polyhedra, from pop-ups that open to 90°, 180°, 270°, or 360°. National Science Foundation (U.S.) (NSF Graduate Research Fellowship) National Science Foundation (U.S.) (NSF ODISSEI grant EFRI-1240383) National Science Foundation (U.S.) (NSF Expedition grant CCF-1138967) National Science Foundation (U.S.) (NSF grant CCF-1161626) National Science Foundation (U.S.) (DARPA/AFOSR grant FA9550-12-1-0423) Natural Sciences and Engineering Research Council of Canada German Research Foundation (DFG) (grant SCHU 2458/1-1) National Science Foundation (U.S.) (NSF grant CCF-0830734) National Science Foundation (U.S.) (NSF grant CBET-0941538) 2014-05-28T15:03:01Z 2014-05-28T15:03:01Z 2013-02 Article http://purl.org/eprint/type/ConferencePaper 978-3-939897-50-7 868-8969 http://hdl.handle.net/1721.1/87552 Abel, Zachary, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, Andre Schulz, Diane L. Souvaine, Giovanni Viglietta, and Andrew Winslow. "Algorithms for Designing Pop-Up Cards." Natacha Portier and Thomas Wilke (Eds.) 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), February 27-March 2, 2013, Kiel, Germany (Leibniz International Proceedings in Informatics (LIPIcs) ; Volume 20). p.269-280. https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-4295-1117 https://orcid.org/0000-0002-3182-1675 en_US http://dx.doi.org/10.4230/LIPIcs.STACS.2013.269 Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) Creative Commons Attribution http://creativecommons.org/ application/pdf Schloss Dagstuhl Publishing International Symposium on Theoretical Aspects of Computer Science |
| spellingShingle | Abel, Zachary Ryan Demaine, Erik D. Demaine, Martin L. Eisenstat, Sarah Charmian Lubiw, Anna Schulz, Andre Souvaine, Diane L. Viglietta, Giovanni Winslow, Andrew Algorithms for Designing Pop-Up Cards |
| title | Algorithms for Designing Pop-Up Cards |
| title_full | Algorithms for Designing Pop-Up Cards |
| title_fullStr | Algorithms for Designing Pop-Up Cards |
| title_full_unstemmed | Algorithms for Designing Pop-Up Cards |
| title_short | Algorithms for Designing Pop-Up Cards |
| title_sort | algorithms for designing pop up cards |
| url | http://hdl.handle.net/1721.1/87552 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-4295-1117 https://orcid.org/0000-0002-3182-1675 |
| work_keys_str_mv | AT abelzacharyryan algorithmsfordesigningpopupcards AT demaineerikd algorithmsfordesigningpopupcards AT demainemartinl algorithmsfordesigningpopupcards AT eisenstatsarahcharmian algorithmsfordesigningpopupcards AT lubiwanna algorithmsfordesigningpopupcards AT schulzandre algorithmsfordesigningpopupcards AT souvainedianel algorithmsfordesigningpopupcards AT vigliettagiovanni algorithmsfordesigningpopupcards AT winslowandrew algorithmsfordesigningpopupcards |