Computational Complexity of Piano-Hinged Dissections

• ABEL Zachary

  MIT Department of Mathematics

• DEMAINE Erik D.

  MIT Computer Science and Artificial Intelligence Laboratory

• DEMAINE Martin L.

  MIT Computer Science and Artificial Intelligence Laboratory

• HORIYAMA Takashi

  Information Technology Center, Saitama University

• UEHARA Ryuhei

  School of Information Science, JAIST

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.

Journal

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E97.A (6), 1206-1212, 2014

  The Institute of Electronics, Information and Communication Engineers

Keywords

• GeoLoop
• hinged dissection
• Ivan's Hinge
• <i>NP</i>-hardness
• paper folding

Details

• CRID: 1390282681287028096
• NII Article ID: 130004770850
• DOI: 10.1587/transfun.e97.a.1206
• ISSN: 17451337
• ISSN: 09168508
• Web Site: http://hdl.handle.net/10119/13776
• Web Site: https://www.jstage.jst.go.jp/article/transfun/E97.A/6/E97.A_1206/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • IRDB
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed