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)


See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated January 15, 2021 by Erik Demaine.