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; Marcel Roeloffzen; Ryuhei Uehara; Yushi Uno

doi:10.1016/j.comgeo.2020.101648

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
, Marcel Roeloffzen
, Ryuhei Uehara
, Yushi Uno

Applied Mathematics and Statistics

Massachusetts Institute of Technology
Tufts University
Nagoya University
The University of Sydney
Eindhoven University of Technology
Japan Advanced Institute of Science and Technology
Osaka Metropolitan University

Research output: Contribution to journal › Article › peer-review

6 Scopus citations

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 language	English
Article number	101648
Journal	Computational Geometry: Theory and Applications
Volume	90
DOIs	https://doi.org/10.1016/j.comgeo.2020.101648
State	Published - Oct 2020

Keywords

Assembly puzzle
NP-complete
Parameterized algorithms

Access to Document

10.1016/j.comgeo.2020.101648

Cite this

@article{10094756795c451dbafc3e866b8bd59b,

title = "Symmetric assembly puzzles are hard, beyond a few pieces",

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.",

keywords = "Assembly puzzle, NP-complete, Parameterized algorithms",

author = "Demaine, \{Erik D.\} and Matias Korman and Ku, \{Jason S.\} and Mitchell, \{Joseph S.B.\} and Yota Otachi and \{van Renssen\}, Andr{\'e} and Marcel Roeloffzen and Ryuhei Uehara and Yushi Uno",

note = "Publisher Copyright: {\textcopyright} 2020",

year = "2020",

month = oct,

doi = "10.1016/j.comgeo.2020.101648",

language = "English",

volume = "90",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

}

TY - JOUR

T1 - Symmetric assembly puzzles are hard, beyond a few pieces

AU - Demaine, Erik D.

AU - Korman, Matias

AU - Ku, Jason S.

AU - Mitchell, Joseph S.B.

AU - Otachi, Yota

AU - van Renssen, André

AU - Roeloffzen, Marcel

AU - Uehara, Ryuhei

AU - Uno, Yushi

PY - 2020/10

Y1 - 2020/10

N2 - 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.

AB - 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.

KW - Assembly puzzle

KW - NP-complete

KW - Parameterized algorithms

UR - https://www.scopus.com/pages/publications/85081991758

U2 - 10.1016/j.comgeo.2020.101648

DO - 10.1016/j.comgeo.2020.101648

M3 - Article

AN - SCOPUS:85081991758

SN - 0925-7721

VL - 90

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

M1 - 101648

ER -

Symmetric assembly puzzles are hard, beyond a few pieces

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this