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: | en_US |
| Published: |
Springer International Publishing
2017
|
| Online Access: | http://hdl.handle.net/1721.1/110865 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-9376-5584 |
| _version_ | 1811071018004905984 |
|---|---|
| author | Korman, Matias Mitchell, Joseph S. B. Otachi, Yota van Renssen, André Roeloffzen, Marcel Uehara, Ryuhei Uno, Yushi 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 Korman, Matias Mitchell, Joseph S. B. Otachi, Yota van Renssen, André Roeloffzen, Marcel Uehara, Ryuhei Uno, Yushi Demaine, Erik D Ku, Jason S |
| author_sort | Korman, Matias |
| 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-23T08:44:50Z |
| format | Article |
| id | mit-1721.1/110865 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:44:50Z |
| publishDate | 2017 |
| publisher | Springer International Publishing |
| record_format | dspace |
| spelling | mit-1721.1/1108652022-09-30T10:59:50Z Symmetric Assembly Puzzles are Hard, Beyond a Few Pieces Korman, Matias Mitchell, Joseph S. B. Otachi, Yota van Renssen, André Roeloffzen, Marcel Uehara, Ryuhei Uno, Yushi Demaine, Erik D Ku, Jason S Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D Ku, Jason S 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. 2017-07-28T13:16:53Z 2017-07-28T13:16:53Z 2016-11 2015-09 Article http://purl.org/eprint/type/ConferencePaper 978-3-319-48531-7 978-3-319-48532-4 0302-9743 1611-3349 http://hdl.handle.net/1721.1/110865 Demaine, Erik D.; Korman, Matias; Ku, Jason S. et al. “Symmetric Assembly Puzzles Are Hard, Beyond a Few Pieces.” Discrete and Computational Geometry and Graphs (2016): 180–192 © 2016 Springer International Publishing https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-9376-5584 en_US http://dx.doi.org/10.1007/978-3-319-48532-4_16 Discrete and Computational Geometry and Graphs Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer International Publishing arXiv |
| spellingShingle | Korman, Matias Mitchell, Joseph S. B. Otachi, Yota van Renssen, André Roeloffzen, Marcel Uehara, Ryuhei Uno, Yushi 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 | http://hdl.handle.net/1721.1/110865 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-9376-5584 |
| work_keys_str_mv | AT kormanmatias symmetricassemblypuzzlesarehardbeyondafewpieces AT mitchelljosephsb symmetricassemblypuzzlesarehardbeyondafewpieces AT otachiyota symmetricassemblypuzzlesarehardbeyondafewpieces AT vanrenssenandre symmetricassemblypuzzlesarehardbeyondafewpieces AT roeloffzenmarcel symmetricassemblypuzzlesarehardbeyondafewpieces AT uehararyuhei symmetricassemblypuzzlesarehardbeyondafewpieces AT unoyushi symmetricassemblypuzzlesarehardbeyondafewpieces AT demaineerikd symmetricassemblypuzzlesarehardbeyondafewpieces AT kujasons symmetricassemblypuzzlesarehardbeyondafewpieces |