Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.comgeo.2020.101648 | Computational Geometry |
Keywords | DocType | Volume |
Assembly puzzle,NP-complete,Parameterized algorithms | Journal | 90 |
ISSN | Citations | PageRank |
0925-7721 | 0 | 0.34 |
References | Authors | |
3 | 9 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Erik D. Demaine | 1 | 4624 | 388.59 |
| Matias Korman | 2 | 178 | 37.28 |
| Jason S. Ku | 3 | 11 | 4.26 |
| Joseph S.B. Mitchell | 4 | 4329 | 428.84 |
| Yota Otachi | 5 | 161 | 37.16 |
| André van Renssen | 6 | 104 | 19.30 |
| Marcel Roeloffzen | 7 | 3 | 3.84 |
| Ryuhei Uehara | 8 | 528 | 75.38 |
| yushi uno | 9 | 222 | 28.80 |