| Autor: |
Demaine, Erik D., Korman, Matias, Ku, Jason S., Mitchell, Joseph S. B., Otachi, Yota, van Renssen, André, Roeloffzen, Marcel, Uehara, Ryuhei, Uno, Yushi |
| Rok vydání: |
2017 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
We study the complexity of symmetric assembly puzzles: given a collection of simple polygons, can we translate, rotate, and possibly flip them so that their interior-disjoint union is line symmetric? On the negative side, we show that the problem is strongly NP-complete even if the pieces are all polyominos. On the positive side, we show that the problem can be solved in polynomial time if the number of pieces is a fixed constant. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
