Paper by Erik D. Demaine

Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, André Schulz, Diane Souvaine, Giovanni Viglietta, and Andrew Winslow, “Algorithms for Designing Pop-Up Cards”, in Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), Kiel, Germany, February 27–March 2, 2013, pages 269–280.

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°.

This paper is also available from DROPS.

Animations of 2D and 3D methods:

Copyright held by the authors. Licensed under the Creative Commons Attribution-No Derivative Works 3.0 license.

The paper is available in PDF (1236k).
See information on file formats.
[Google Scholar search]

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated March 27, 2017 by Erik Demaine.