Computational Complexity of Piano-Hinged Dissections

Zachary ABEL  Erik D. DEMAINE  Martin L. DEMAINE  Takashi HORIYAMA  Ryuhei UEHARA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E97-A   No.6   pp.1206-1212
Publication Date: 2014/06/01
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: 
Keyword: 
GeoLoop,  hinged dissection,  Ivan's Hinge,  NP-hardness,  paper folding,  

Full Text: PDF(2.3MB)
>>Buy this Article

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.