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.

BibTeX

@Article{Symmetric_CGTA,
  AUTHOR        = {Erik D. Demaine and Matias Korman and Jason S. Ku and Joseph S. B. Mitchell and Yota Otachi and Andr\'e van Renssen and Marcel Roeloffzen and Ryuhei Uehara and Yushi Uno},
  TITLE         = {Symmetric assembly puzzles are hard, beyond a few pieces},
  JOURNAL       = {Computational Geometry: Theory and Applications},
  journalurl    = {https://www.sciencedirect.com/journal/computational-geometry},
  VOLUME        = 90,
  MONTH         = {October},
  YEAR          = 2020,
  PAGES         = {Article 101648},

  doi           = {https://dx.doi.org/10.1016/J.COMGEO.2020.101648},
  dblp          = {https://dblp.org/rec/journals/comgeo/DemaineKKMORRUU20},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1016/j.comgeo.2020.101648">ScienceDirect</A> and as <A HREF="https://arXiv.org/abs/1703.02671">arXiv:1703.02671</A>.},
  replaces      = {Symmetric_JCDCGG2015full},
  papers        = {Symmetric_JCDCGG2015full},
  withstudent   = 1,
}

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)