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

Full description

Bibliographic Details
Main Authors: Demaine, Erik D, Ku, Jason S
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:English
Published: Elsevier BV 2020
Online Access:https://hdl.handle.net/1721.1/128811