Computational Complexity of Piano-Hinged Dissections
Summary :
We prove NP-completeness of deciding whether a given loop of colored right isosceles triangles, hinged together at edges, can be folded into a specified rectangular three-color pattern. By contrast, the same problem becomes polynomially solvable with one color or when the target shape is a tree-shaped polyomino.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E97-A No.6 pp.1206-1212
- Publication Date
- 2014/06/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E97.A.1206
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Zachary ABEL
MIT Department of Mathematics
Erik D. DEMAINE
MIT Computer Science and Artificial Intelligence Laboratory
Martin L. DEMAINE
MIT Computer Science and Artificial Intelligence Laboratory
Takashi HORIYAMA
Saitama University
Ryuhei UEHARA
JAIST
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Zachary ABEL, Erik D. DEMAINE, Martin L. DEMAINE, Takashi HORIYAMA, Ryuhei UEHARA, "Computational Complexity of Piano-Hinged Dissections" in IEICE TRANSACTIONS on Fundamentals,
vol. E97-A, no. 6, pp. 1206-1212, June 2014, doi: 10.1587/transfun.E97.A.1206.
Abstract: We prove NP-completeness of deciding whether a given loop of colored right isosceles triangles, hinged together at edges, can be folded into a specified rectangular three-color pattern. By contrast, the same problem becomes polynomially solvable with one color or when the target shape is a tree-shaped polyomino.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.1206/_p
Copy
@ARTICLE{e97-a_6_1206,
author={Zachary ABEL, Erik D. DEMAINE, Martin L. DEMAINE, Takashi HORIYAMA, Ryuhei UEHARA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Computational Complexity of Piano-Hinged Dissections},
year={2014},
volume={E97-A},
number={6},
pages={1206-1212},
abstract={We prove NP-completeness of deciding whether a given loop of colored right isosceles triangles, hinged together at edges, can be folded into a specified rectangular three-color pattern. By contrast, the same problem becomes polynomially solvable with one color or when the target shape is a tree-shaped polyomino.},
keywords={},
doi={10.1587/transfun.E97.A.1206},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - Computational Complexity of Piano-Hinged Dissections
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1206
EP - 1212
AU - Zachary ABEL
AU - Erik D. DEMAINE
AU - Martin L. DEMAINE
AU - Takashi HORIYAMA
AU - Ryuhei UEHARA
PY - 2014
DO - 10.1587/transfun.E97.A.1206
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2014
AB - We prove NP-completeness of deciding whether a given loop of colored right isosceles triangles, hinged together at edges, can be folded into a specified rectangular three-color pattern. By contrast, the same problem becomes polynomially solvable with one color or when the target shape is a tree-shaped polyomino.
ER -
English
