Paper by Erik D. Demaine

Erik D. Demaine, Matias Korman, Jason S. Ku, Joseph S. B. Mitchell, Yota Otachi, André van Renssen, Marcel Roeloffzen, Ryuhei Uehara, and Yushi Uno, “Symmetric assembly puzzles are hard, beyond a few pieces”, Computational Geometry: Theory and Applications, volume 90, October 2020, Article 101648.

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.

This paper is also available from ScienceDirect and as arXiv:1703.02671.

The paper is available in PDF (521k).
See information on file formats.
[Google Scholar search]

Related papers:
Symmetric_JCDCGG2015full (Symmetric assembly puzzles are hard, beyond a few pieces)

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated March 12, 2024 by Erik Demaine.