2026-07-20T07:32:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3940 2024-03-06T10:34:40Z ddc:004 open_access

Algorithms for Designing Pop-Up Cards Abel, Zachary Demaine, Erik D. Demaine, Martin L. Eisenstat, Sarah Lubiw, Anna Schulz, André Souvaine, Diane L. Viglietta, Giovanni Winslow, Andrew geometric folding linkages universality 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°. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zachary Abel and Erik D. Demaine and Martin L. Demaine and Sarah Eisenstat and Anna Lubiw and André Schulz and Diane L. Souvaine and Giovanni Viglietta and Andrew Winslow 2013 Is Part Of LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2013.269 urn:nbn:de:0030-drops-39407 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.269 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode