Symmetric assembly puzzles are hard, beyond a few pieces

Erik D. Demaine, Matias Korman, Jason S. Ku, Joseph S.B. Mitchell, Yota Otachi, André van Renssen (Corresponding author), Marcel Roeloffzen, Ryuhei Uehara, Yushi Uno

Research output: Contribution to journalArticleAcademicpeer-review

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.

Original languageEnglish
Article number101648
Number of pages11
JournalComputational Geometry: Theory and Applications
Volume90
DOIs
Publication statusPublished - Oct 2020

Keywords

  • Assembly puzzle
  • NP-complete
  • Parameterized algorithms

Fingerprint Dive into the research topics of 'Symmetric assembly puzzles are hard, beyond a few pieces'. Together they form a unique fingerprint.

Cite this