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.

BibTeX

@InProceedings{PianoHinged_EuroCG2013,
  AUTHOR        = {Zachary Abel and Erik D. Demaine and Martin L. Demaine and Takashi Horiyama and Ryuhei Uehara},
  TITLE         = {Computational Complexity of Piano-Hinged Dissections},
  BOOKTITLE     = {Abstracts from the 29th European Workshop on Computational
                   Geometry (EuroCG 2013)},
  bookurl       = {http://www.ibr.cs.tu-bs.de/alg/eurocg13/},
  ADDRESS       = {Braunschweig, Germany},
  MONTH         = {March 17--20},
  YEAR          = 2013,
  PAGES         = {147--150},

  paperkind     = {abstract},
  unrefereed    = 1,
  comments      = {This abstract is also available from <A HREF="http://hdl.handle.net/10119/11620">JAIST DSPACE</A>.},
  length        = {4 pages},
  papers        = {PianoHinged_IEICE},
}

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)