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”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, volume E97-A, number 6, 2014, pages 1206–1212.

BibTeX

@Article{PianoHinged_IEICE,
  AUTHOR        = {Zachary Abel and Erik D. Demaine and Martin L. Demaine and Takashi Horiyama and Ryuhei Uehara},
  TITLE         = {Computational Complexity of Piano-Hinged Dissections},
  JOURNAL       = {IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences},
  VOLUME        = {E97-A},
  NUMBER        = 6,
  PAGES         = {1206--1212},
  YEAR          = 2014,

  doi           = {https://dx.doi.org/10.1587/transfun.E97.A.1206},
  dblp          = {https://dblp.org/rec/journals/ieicet/AbelDDHU14},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1587/transfun.E97.A.1206">J-STAGE</A>.},
  length        = {7 pages},
  replaces      = {PianoHinged_EuroCG2013},
  papers        = {PianoHinged_EuroCG2013},
}

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 paper is also available from J-STAGE.

Length:

The paper is 7 pages.

Availability:

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)