Paper by Erik D. Demaine

Reference:

Hugo A. Akitaya, Erik D. Demaine, Takashi Horiyama, Thomas C. Hull, Jason S. Ku, and Tomohiro Tachi, “Rigid Foldability is NP-hard”, Journal of Computational Geometry, volume 11, number 1, 2020, pages 93–124.

BibTeX

@Article{RigidOrigamiHard_JoCG,
  AUTHOR        = {Hugo A. Akitaya and Erik D. Demaine and Takashi Horiyama and Thomas C. Hull and Jason S. Ku and Tomohiro Tachi},
  TITLE         = {Rigid Foldability is {NP}-hard},
  JOURNAL       = {Journal of Computational Geometry},
  journalurl    = {http://jocg.org/},
  VOLUME        = 11,
  NUMBER        = 1,
  YEAR          = 2020,
  PAGES         = {93--124},

  withstudent   = 1,
  doi           = {https://dx.doi.org/10.20382/jocg.v11i1a4},
  dblp          = {https://dblp.org/rec/journals/jocg/AkitayaDHHKT20},
  comments      = {This paper is also available as <A HREF="https://arXiv.org/abs/1812.01160">arXiv:1812.01160</A>, and from <A HREF="https://doi.org/10.20382/jocg.v11i1a4">JoCG</A>.},
}

Abstract:

We prove NP-hardness of deciding rigid foldability, that is, whether a sheet of material can be folded by bending only at prescribed creases while all regions between the creases undergo a rigid motion, like rigid plates connected at hinges. First, given a degree-4 flat-foldable crease pattern, deciding whether exactly those creases can be flexed (with every specified crease bending nontrivially), up to a given ε accuracy, is weakly NP-complete by a reduction from Partition. Second, given a crease pattern, deciding whether there is a rigid folding bending at any nonempty subset of those creases (i.e., where each crease is optional) is strongly NP-hard by a reduction from Positive 1-in-E3 SAT. Both results hold when just looking for a small motion adjacent to the unfolded 2D state, where there is no potential for self-intersection of the material. Thus our results are quite unlike existing NP-hardness results for flat foldability of crease patterns, where the complexity originates from finding a layer ordering that avoids self-intersection. Rather, our hardness proofs exploit the multiple combinatorial behaviors of rigid foldings locally at each vertex. These results justify why rigid origami has been so difficult to analyze mathematically, and help explain why it is often harder to fold from an unfolded sheet than to unfold a folded state back to 2D, a problem frequently encountered when realizing folding-based systems such as self-folding matter and reconfigurable robots.

Comments:

This paper is also available as arXiv:1812.01160, and from JoCG.

Availability:

The paper is available in PDF (7791k).

See information on file formats.

[Google Scholar search]