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”, in Revised Papers from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Lecture Notes in Computer Science, volume 9943, Kyoto, Japan, September 14–16, 2015, pages 180–192.

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

Availability:

The paper is available in PDF (394k).

See information on file formats.

[Google Scholar search]

Related papers:

Symmetric_CGTA (Symmetric assembly puzzles are hard, beyond a few pieces)

Symmetric_JCDCGG2015 (Symmetric assembly puzzles are hard, beyond a few pieces)