Symmetric Assembly Puzzles are Hard, Beyond a Few Pieces

Symmetric Assembly Puzzles are Hard, Beyond a Few Pieces

Show other versions (1)

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...

Full description

Bibliographic Details
Main Authors: Korman, Matias, Mitchell, Joseph S. B., Otachi, Yota, van Renssen, André, Roeloffzen, Marcel, Uehara, Ryuhei, Uno, Yushi, Demaine, Erik D, Ku, Jason S
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
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

Internet

http://hdl.handle.net/1721.1/110865
https://orcid.org/0000-0003-3803-5703
https://orcid.org/0000-0002-9376-5584

Similar Items