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...
Na minha lista:
| Principais autores: | , , , , , |
|---|---|
| Formato: | Artigo |
| Idioma: | Inglês |
| Publicado em: |
Carleton University
2020-06-01
|
| coleção: | Journal of Computational Geometry |
| Acesso em linha: | https://jocg.org/index.php/jocg/article/view/3094 |
| Tags: |
Sem tags, seja o primeiro a adicionar uma tag!
|