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
Last updated January 15, 2021 by