Paper by Erik D. Demaine
- Reference:
- Erik D. Demaine, David Eppstein, Adam Hesterberg, Hiro Ito, Anna Lubiw, Ryuhei Uehara, and Yushi Uno, “Folding a Paper Strip to Minimize Thickness”, in Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM 2015), Lecture Notes in Computer Science, volume 8973, Dhaka, Bangladesh, February 26–28, 2015, pages 113–124.
- Abstract:
-
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 the first problem fixed-parameter tractable
in 1D with respect to the number of layers.
- Comments:
- This paper is also available from SpringerLink.
- Availability:
- The paper is available in PDF (322k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Thickness_JDA (Folding a Paper Strip to Minimize Thickness)
See also other papers by Erik Demaine.
These pages are generated automagically from a
BibTeX file.
Last updated July 23, 2024 by
Erik Demaine.