Paper by Erik D. Demaine

Reference:

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.

Abstract:

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.

Comments:

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

Availability:

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)