Paper by Erik D. Demaine

Reference:

Hugo A. Akitaya, Erik D. Demaine, and Jason S. Ku, “Simple Folding is Really Hard”, Journal of Information Processing, volume 25, 2017, pages 580–589. Special issue of papers from the 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games

Abstract:

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.

Comments:

This paper is also available from J-STAGE.

Length:

The paper is 10 pages.

Availability:

The paper is available in PDF (1172k).

See information on file formats.

[Google Scholar search]

Related papers:

SimpleFolds_JCDCGGG2016 (Simple Folding is Really Hard)