**Reference**:- Jean Cardinal, Erik D. Demaine, Martin L. Demaine, Shinji Imahori, Stefan Langerman, and Ryuhei Uehara, “Algorithmic Folding Complexity”, in
*Abstracts from the 7th Japan Conference on Computational Geometry and Graphs (JCCGG 2009)*, Kanazawa, Ishikawa, Japan, November 11–13, 2009, to appear. **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 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 polylogarithmic in*n*. We also show that the maximum possible folding complexity of any string of length*n*is*O*(*n*/lg*n*), meeting a previously known lower bound. **Length**:- The paper is 2 pages.
**Availability**:- The paper is available in PDF (372k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- PleatFolding_GC (Algorithmic Folding Complexity)
- PleatFolding_ISAAC2009 (Algorithmic Folding Complexity)

See also other papers by Erik Demaine.

Last updated May 13, 2021 by Erik Demaine.