**Reference**:- Jean Cardinal, Erik D. Demaine, Martin L. Demaine, Shinji Imahori, Tsuyoshi Ito, Masashi Kiyomi, Stefan Langerman, Ryuhei Uehara, and Takeaki Uno, “Algorithmic Folding Complexity”,
*Graphs and Combinatorics*, volume 27, number 3, 2011, pages 341–351. **Abstract**:-
How do we most quickly fold a paper strip (modeled as a line) to obtain a
desired mountain-valley pattern of equidistant creases (viewed as a binary
string)? Define the
*folding complexity*of a mountain-valley string as the minimum number of simple folds required to construct it. We first show that the folding complexity of a length-*n**uniform*string (all mountains or all valleys), and hence of a length-*n**pleat*(alternating mountain/valley), is*O*(lg^{2}*n*). We also show that a lower bound of the complexity of the problems is Ω(lg^{2}*n*/lg lg*n*). Next we show that almost all mountain-valley patterns require Ω(*n*/lg*n*) folds, which means that the uniform and pleat foldings are relatively easy problems. We also give a general algorithm for folding an arbitrary sequence of length*n*in*O*(*n*/lg*n*) folds, meeting the lower bound up to a constant factor. **Comments**:- This paper is also available from SpringerLink.
**Availability**:- The paper is available in PDF (383k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- PleatFolding_ISAAC2009 (Algorithmic Folding Complexity)
- PleatFolding_JCCGG2009 (Algorithmic Folding Complexity)

See also other papers by Erik Demaine.

Last updated September 2, 2021 by Erik Demaine.