Paper by Erik D. Demaine
- Erik D. Demaine, David Eppstein, Adam Hesterberg, Hiro Ito, Anna Lubiw, Ryuhei Uehara, and Yushi Uno, “Folding a Paper Strip to Minimize Thickness”, Journal of Discrete Algorithms, volume 36, January 2016, pages 18–26.
In this paper, we study how to fold a specified origami crease pattern in
order to minimize the impact of paper thickness. Specifically, origami designs
are often expressed by a mountain-valley pattern (plane graph of creases with
relative fold orientations), but in general this specification is consistent
with exponentially many possible folded states. We analyze the complexity of
finding the best consistent folded state according to two metrics: minimizing
the total number of layers in the folded state (so that a “flat
folding” is indeed close to flat), and minimizing the total amount of
paper required to execute the folding (where “thicker” creases
consume more paper). We prove both problems strongly NP-complete even for 1D
folding. On the other hand, we prove both problems fixed-parameter tractable
in 1D with respect to the number of layers.
- This paper is also available from ScienceDirect.
- The paper is available in PDF (184k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Thickness_WALCOM2015 (Folding a Paper Strip to Minimize Thickness)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated January 18, 2021 by