Symmetric assembly puzzles are hard, beyond a few pieces
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 po...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Elsevier BV
2020
|
| Online Access: | https://hdl.handle.net/1721.1/128811 |
| _version_ | 1826209651150028800 |
|---|---|
| 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 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. |
| first_indexed | 2024-09-23T14:26:03Z |
| format | Article |
| id | mit-1721.1/128811 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:26:03Z |
| publishDate | 2020 |
| publisher | Elsevier BV |
| record_format | dspace |
| spelling | mit-1721.1/1288112022-10-01T21:19:43Z Symmetric assembly puzzles are hard, beyond a few pieces Demaine, Erik D Ku, Jason S Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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. 2020-12-11T14:31:53Z 2020-12-11T14:31:53Z 2020-10 2020-12-09T17:27:36Z Article http://purl.org/eprint/type/JournalArticle 0925-7721 https://hdl.handle.net/1721.1/128811 Demaine, Erik D. et al. “Symmetric assembly puzzles are hard, beyond a few pieces.” Computer methods in applied mechanics and engineering, 90 (October 2020): 101648 © 2020 The Author(s) en 10.1016/J.COMGEO.2020.101648 Computational Geometry: Theory and Applications Creative Commons Attribution-NonCommercial-NoDerivs License http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier BV arXiv |
| spellingShingle | Demaine, Erik D Ku, Jason S Symmetric assembly puzzles are hard, beyond a few pieces |
| title | Symmetric assembly puzzles are hard, beyond a few pieces |
| title_full | Symmetric assembly puzzles are hard, beyond a few pieces |
| title_fullStr | Symmetric assembly puzzles are hard, beyond a few pieces |
| title_full_unstemmed | Symmetric assembly puzzles are hard, beyond a few pieces |
| title_short | Symmetric assembly puzzles are hard, beyond a few pieces |
| title_sort | symmetric assembly puzzles are hard beyond a few pieces |
| url | https://hdl.handle.net/1721.1/128811 |
| work_keys_str_mv | AT demaineerikd symmetricassemblypuzzlesarehardbeyondafewpieces AT kujasons symmetricassemblypuzzlesarehardbeyondafewpieces |