**Reference**:- Josh Brunner, Erik D. Demaine, Della 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
--- deciding which crease patterns can be folded flat by a sequence of (some model of) simple folds. We give new efficient algorithms for*simple foldability problem*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.*mixed* **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.

Last updated May 16, 2024 by Erik Demaine.