|
For Full-Text PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
|
Computational Complexity of Piano-Hinged Dissections
Zachary ABEL Erik D. DEMAINE Martin L. DEMAINE Takashi HORIYAMA Ryuhei UEHARA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E97-A
No.6
pp.1206-1212 Publication Date: 2014/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E97.A.1206
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: GeoLoop, hinged dissection, Ivan's Hinge, NP-hardness, paper folding,
Full Text: PDF(2.3MB) >>Buy this Article
Summary:
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.
|
|