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.

BibTeX

@InProceedings{MixedSimpleFolds_TJCDCGGG2021,
  AUTHOR        = {Josh Brunner and Erik D. Demaine and Della Hendrickson and Victor Luo and Andy Tockman},
  authororig    = {Josh Brunner and Erik D. Demaine and Dylan Hendrickson and Victor Luo and Andy Tockman},
  TITLE         = {Complexity of Simple Folding Orthogonal Crease Patterns},
  BOOKTITLE     = {Abstracts from the 23rd Thailand-Japan Conference on Discrete and Computational Geometry, Graphs, and Games (TJCDCGGG 2021)},
  bookurl       = {https://www.math.science.cmu.ac.th/tjcdcggg/},
  MONTH         = {September 3--5},
  YEAR          = 2021,
  PAGES         = {26--27},

  paperkind     = {abstract},
  unrefereed    = 1,
  withstudent   = 1,
  papers        = {MixedSimpleFolds_TJM},
}

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)