1-1hit |
Zachary ABEL Erik D. DEMAINE Martin L. DEMAINE Takashi HORIYAMA Ryuhei UEHARA
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.