Paper by Erik D. Demaine
- Jason S. Ku, Erik D. Demaine, Matias Korman, Joseph 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.
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 SpringerLink.
- The paper is available in PDF (394k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Symmetric_JCDCGG2015 (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 June 22, 2017 by