Paper by Erik D. Demaine
- Josh Brunner, Erik D. Demaine, Dylan Hendrickson, Victor Luo, and Andy Tockman, “Complexity of Simple Folding of Mixed Orthogonal Crease Patterns”, Thai Journal of Mathematics, to appear.
Continuing results from JCDCGGG 2016 and 2017, we solve several new cases of
the simple foldability 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 orthogonal one-layer simple folds.
By contrast, we show strong NP-completeness for mixed orthogonal 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 paper.
- The paper is available in PDF (732k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- MixedSimpleFolds_TJCDCGGG2021 (Complexity of Simple Folding Orthogonal Crease Patterns)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated November 6, 2023 by