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.1007/978-3-319-48532-4_16

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

Stony Brook University

Massachusetts Institute of Technology
Tohoku University
Japan Advanced Institute of Science and Technology
National Institute of Informatics
Japan Science and Technology Agency
Osaka Metropolitan University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 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
Title of host publication	Discrete and Computational Geometry and Graphs - 18th Japan Conference, JCDCGG 2015, Revised Selected Papers
Editors	Toshinori Sakai, Hiro Ito, Jin Akiyama
Publisher	Springer Verlag
Pages	180-192
Number of pages	13
ISBN (Print)	9783319485317
DOIs	https://doi.org/10.1007/978-3-319-48532-4_16
State	Published - 2016
Event	18th Japan Conference on Discrete and Computational Geometry and Graphs, JCDCGG 2015 - Kyoto, Japan Duration: Sep 14 2015 → Sep 16 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9943 LNCS

Conference

Conference	18th Japan Conference on Discrete and Computational Geometry and Graphs, JCDCGG 2015
Country/Territory	Japan
City	Kyoto
Period	09/14/15 → 09/16/15

Access to Document

10.1007/978-3-319-48532-4_16

Cite this

Demaine, E. D., Korman, M., Ku, J. S., Mitchell, J. S. B., Otachi, Y., Renssen, A., Roeloffzen, M., Uehara, R., & Uno, Y. (2016). Symmetric assembly puzzles are hard, beyond a few pieces. In T. Sakai, H. Ito, & J. Akiyama (Eds.), Discrete and Computational Geometry and Graphs - 18th Japan Conference, JCDCGG 2015, Revised Selected Papers (pp. 180-192). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9943 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-48532-4_16

Demaine, Erik D. ; Korman, Matias ; Ku, Jason S. et al. / Symmetric assembly puzzles are hard, beyond a few pieces. Discrete and Computational Geometry and Graphs - 18th Japan Conference, JCDCGG 2015, Revised Selected Papers. editor / Toshinori Sakai ; Hiro Ito ; Jin Akiyama. Springer Verlag, 2016. pp. 180-192 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{50a14f1f42cb41d8b1ce758e54687f27,

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

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

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2016.; 18th Japan Conference on Discrete and Computational Geometry and Graphs, JCDCGG 2015 ; Conference date: 14-09-2015 Through 16-09-2015",

year = "2016",

doi = "10.1007/978-3-319-48532-4\_16",

language = "English",

isbn = "9783319485317",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "180--192",

editor = "Toshinori Sakai and Hiro Ito and Jin Akiyama",

booktitle = "Discrete and Computational Geometry and Graphs - 18th Japan Conference, JCDCGG 2015, Revised Selected Papers",

}

Demaine, ED, Korman, M, Ku, JS, Mitchell, JSB, Otachi, Y, Renssen, A, Roeloffzen, M, Uehara, R & Uno, Y 2016, Symmetric assembly puzzles are hard, beyond a few pieces. in T Sakai, H Ito & J Akiyama (eds), Discrete and Computational Geometry and Graphs - 18th Japan Conference, JCDCGG 2015, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9943 LNCS, Springer Verlag, pp. 180-192, 18th Japan Conference on Discrete and Computational Geometry and Graphs, JCDCGG 2015, Kyoto, Japan, 09/14/15. https://doi.org/10.1007/978-3-319-48532-4_16

Symmetric assembly puzzles are hard, beyond a few pieces. / Demaine, Erik D.; Korman, Matias; Ku, Jason S. et al.
Discrete and Computational Geometry and Graphs - 18th Japan Conference, JCDCGG 2015, Revised Selected Papers. ed. / Toshinori Sakai; Hiro Ito; Jin Akiyama. Springer Verlag, 2016. p. 180-192 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9943 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

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 - Renssen, Andrévan

AU - Roeloffzen, Marcel

AU - Uehara, Ryuhei

AU - Uno, Yushi

PY - 2016

Y1 - 2016

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.

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

U2 - 10.1007/978-3-319-48532-4_16

DO - 10.1007/978-3-319-48532-4_16

M3 - Conference contribution

SN - 9783319485317

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 180

EP - 192

BT - Discrete and Computational Geometry and Graphs - 18th Japan Conference, JCDCGG 2015, Revised Selected Papers

A2 - Sakai, Toshinori

A2 - Ito, Hiro

A2 - Akiyama, Jin

PB - Springer Verlag

T2 - 18th Japan Conference on Discrete and Computational Geometry and Graphs, JCDCGG 2015

Y2 - 14 September 2015 through 16 September 2015

ER -

Demaine ED, Korman M, Ku JS, Mitchell JSB, Otachi Y, Renssen A et al. Symmetric assembly puzzles are hard, beyond a few pieces. In Sakai T, Ito H, Akiyama J, editors, Discrete and Computational Geometry and Graphs - 18th Japan Conference, JCDCGG 2015, Revised Selected Papers. Springer Verlag. 2016. p. 180-192. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-48532-4_16

Symmetric assembly puzzles are hard, beyond a few pieces

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this