Paper by Erik D. Demaine

Zachary Abel, Erik D. Demaine, Martin L. Demaine, Takashi Horiyama, and Ryuhei Uehara, “Computational Complexity of Piano-Hinged Dissections”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, volume E97-A, number 6, 2014, pages 1206–1212.

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.

This paper is also available from IEICE.

The paper is 7 pages.

The paper is available in PDF (2324k).
See information on file formats.
[Google Scholar search]

Related papers:
PianoHinged_EuroCG2013 (Computational Complexity of Piano-Hinged Dissections)

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated May 17, 2017 by Erik Demaine.