Paper by Erik D. Demaine

Reference:
Zachary Abel, Erik D. Demaine, Martin L. Demaine, Takashi Horiyama, and Ryuhei Uehara, “Computational Complexity of Piano-Hinged Dissections”, in Abstracts from the 29th European Workshop on Computational Geometry (EuroCG 2013), Braunschweig, Germany, March 17–20, 2013, pages 147–150.

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.

Comments:
This abstract is also available from JAIST DSPACE.

Length:
The abstract is 4 pages.

Availability:
The abstract is available in PDF (1208k).
See information on file formats.
[Google Scholar search]

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


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