Paper by Erik D. Demaine
- Josh Brunner, Erik D. Demaine, Dylan Hendrickson, Victor Luo, and Andy Tockman, “Complexity of Simple Folding Orthogonal Crease Patterns”, in Abstracts from the 23rd Thailand-Japan Conference on Discrete and Computational Geometry, Graphs, and Games (TJCDCGGG 2021), September 3–5, 2021, pages 26–27.
Continuing results from JCDCGGG 2016 and 2017, we solve several new cases of
the simple folding problem — deciding which crease patterns can
be folded flat by a sequence of (some model of) simple folds. We give new
efficient algorithms for mixed crease patterns, where some creases are
assigned mountain/valley while others are unassigned, for all 1D cases and for
2D rectangular paper with one-layer simple folds. By contrast, we show strong
NP-completeness for mixed crease patterns on 2D rectangular paper with
some-layers simple folds, complementing a previous result for all-layers
simple folds. We also prove strong NP-completeness for finite simple folds
(no matter the number of layers) of unassigned orthogonal crease patterns on
arbitrary paper, complementing a previous result for assigned crease patterns,
and contrasting with a previous positive result for infinite all-layers simple
folds. In total, we obtain a characterization of polynomial vs. NP-hard for
all cases — finite/infinite one/some/all-layers simple folds of
assigned/unassigned/mixed orthogonal crease patterns on
1D/rectangular/arbitrary paper — except the unsolved case of infinite
all-layers simple folds of assigned orthogonal crease patterns on arbitrary
- The abstract is available in PDF (262k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated May 1, 2023 by