Computational Complexity of Piano-Hinged Dissections

• Abel, Zachary

• Demaine, Erik D.

• Demaine, Martin L.

• Horiyama, Takashi

• Uehara, Ryuhei

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.

March 17-20, 2013, Braunschweig, Germany

identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/11620

Journal

• The 29th European Workshop on Computational Geometry (EuroCG 2013)

  The 29th European Workshop on Computational Geometry (EuroCG 2013) 147-150, 2013-03

Keywords

• Piano-hinged dissection
• paper folding
• computational complexity
• NP-completeness

Details

• CRID: 1050855522108887296
• NII Article ID: 120006675376
• Web Site: http://hdl.handle.net/10119/11620
• Text Lang: en
• Article Type: conference paper
• Data Source:
  • IRDB
  • CiNii Articles