Rigid foldability is NP-hard
In this paper, we show that the rigid-foldability of a given crease pattern using all creases is weakly NP-hard by a reduction from the partition problem, and that rigid-foldability with optional creases is NP-hard by a reduction from the 1-in-3 SAT problem. Unlike flat-foldabilty of origami or flex...
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Artigo |
| Lingua: | Inglês |
| Pubblicazione: |
Carleton University
2020-06-01
|
| Serie: | Journal of Computational Geometry |
| Accesso online: | https://jocg.org/index.php/jocg/article/view/3094 |
| Tags: |
Nessun Tag, puoi essere il primo ad aggiungerne!!
|