Paper by Erik D. Demaine
- Reference:
- Josh Brunner, Erik D. Demaine, Della 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.
- Abstract:
-
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
paper.
- Availability:
- The abstract is available in PDF (262k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- MixedSimpleFolds_TJM (Complexity of Simple Folding of Mixed Orthogonal Crease Patterns)
See also other papers by Erik Demaine.
These pages are generated automagically from a
BibTeX file.
Last updated July 23, 2024 by
Erik Demaine.