Paper by Martin L. Demaine
- 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.
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
- This paper is also available from IEICE.
- The paper is 7 pages.
- Currently unavailable. If you are in a rush for copies,
- [Google Scholar search]
- Related papers:
- PianoHinged_EuroCG2013 (Computational Complexity of Piano-Hinged Dissections)
See also other papers by Martin Demaine.
These pages are generated automagically from a
Last updated November 20, 2018 by