Paper by Erik D. Demaine

Reference:
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.

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

Comments:
This paper is also available from DROPS.

Animations of 2D and 3D methods:


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

Availability:
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 July 25, 2017 by Erik Demaine.