Paper by Erik D. Demaine
- 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.
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.
- This paper is also available from JoCG.
- The paper is available in PDF (7791k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated October 17, 2021 by