Paper by Erik D. Demaine
- Hugo Akitaya, Erik D. Demaine, and Jason S. Ku, “Simple Folding is Really Hard”, Journal of Information Processing, to appear. Special issue of papers from the 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games
Simple folding (folding along one line at a time) is a practical form of
origami used in manufacturing such as sheet metal bending. We prove strong
NP-completeness of deciding whether a crease pattern can be simply folded,
both for orthogonal paper with assigned orthogonal creases and for square
paper with assigned or unassigned creases at multiples of 45°. These
results settle a long standing open problem, where weak NP-hardness was
established for a subset of the models considered here, leaving open the
possibility of pseudopolynomial-time algorithms. We also formalize and
generalize the previously proposed simple folding models, and introduce new
infinite simple-fold models motivated by practical manufacturing. In the
infinite models, we extend our strong NP-hardness results, as well as
polynomial-time algorithms for rectangular paper with assigned or unassigned
orthogonal creases (map folding). These results motivate why rectangular maps
have orthogonal but not diagonal creases.
- The paper is 10 pages.
- The paper is available in PDF (1297k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- SimpleFolds_JCDCGGG2016 (Simple Folding is Really Hard)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated July 25, 2017 by