Paper by Erik D. Demaine
- Reference:
- 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.
- Abstract:
-
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.
- Availability:
- 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
BibTeX file.
Last updated September 20, 2023 by
Erik Demaine.