Rigid foldability is NP-hard
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, deci...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2020
|
| Online Access: | https://hdl.handle.net/1721.1/128807 |
| _version_ | 1811077880846745600 |
|---|---|
| author | Demaine, Erik D Ku, Jason S |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D Ku, Jason S |
| author_sort | Demaine, Erik D |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T10:49:45Z |
| format | Article |
| id | mit-1721.1/128807 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:49:45Z |
| publishDate | 2020 |
| record_format | dspace |
| spelling | mit-1721.1/1288072022-09-30T23:19:34Z Rigid foldability is NP-hard Demaine, Erik D Ku, Jason S Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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. 2020-12-11T12:32:27Z 2020-12-11T12:32:27Z 2020 2018-12 2020-12-09T17:06:43Z Article http://purl.org/eprint/type/JournalArticle 1920-180X https://hdl.handle.net/1721.1/128807 Akitaya, Hugo A. et al. “Rigid foldability is NP-hard.” Journal of Computational Geometry, 11, 1 (2020): 93-124 © 2020 The Author(s) en Journal of Computational Geometry Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf Journal of Computational Geometry |
| spellingShingle | Demaine, Erik D Ku, Jason S Rigid foldability is NP-hard |
| title | Rigid foldability is NP-hard |
| title_full | Rigid foldability is NP-hard |
| title_fullStr | Rigid foldability is NP-hard |
| title_full_unstemmed | Rigid foldability is NP-hard |
| title_short | Rigid foldability is NP-hard |
| title_sort | rigid foldability is np hard |
| url | https://hdl.handle.net/1721.1/128807 |
| work_keys_str_mv | AT demaineerikd rigidfoldabilityisnphard AT kujasons rigidfoldabilityisnphard |