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.

BibTeX

@InProceedings{Popups_STACS2013,
  AUTHOR        = {Zachary Abel and Erik D. Demaine and Martin L. Demaine and Sarah Eisenstat and Anna Lubiw and Andr\'e Schulz and Diane Souvaine and Giovanni Viglietta and Andrew Winslow},
  TITLE         = {Algorithms for Designing Pop-Up Cards},
  BOOKTITLE     = {Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  bookurl       = {http://www.stacs2013.uni-kiel.de},
  ADDRESS       = {Kiel, Germany},
  MONTH         = {February 27--March 2},
  YEAR          = 2013,
  PAGES         = {269--280},

  withstudent   = 1,
  doi           = {https://dx.doi.org/10.4230/LIPIcs.STACS.2013.269},
  dblp          = {https://dblp.org/rec/conf/stacs/AbelDDELSSVW13},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.4230/LIPIcs.STACS.2013.269">LIPIcs</A>.
<P>
Animations of 2D and 3D methods:
<P>
<TABLE><TR>
<TD>
<IMG SRC="butterfly2.gif"/><BR>
<IMG SRC="castle.gif"/>
<TD>
<IMG STYLE="padding-left: 1em" SRC="fish2.gif"/>
</TABLE>
},
  copyright     = {Copyright held by the authors.  Licensed under the
                   <A HREF="http://creativecommons.org/licenses/by-nd/3.0/">Creative Commons Attribution-No Derivative Works 3.0</A> license.},
}

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

Animations of 2D and 3D methods:

Copyright:

Availability:

The paper is available in PDF (1236k).

See information on file formats.

[Google Scholar search]