**Reference**:- Jean Cardinal, Erik D. Demaine, Martin L. Demaine, Shinji Imahori, Stefan Langerman, and Ryuhei Uehara, “Algorithmic Folding Complexity”, in
*Proceedings of the 20th Annual International Symposium on Algorithms and Computation (ISAAC 2009)*, Lecture Notes in Computer Science, volume 5878, Hawaii, USA, December 16–18, 2009, pages 452–461. **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. **Comments**:- This paper is also available from SpringerLink.
**Availability**:- The paper is available in PDF (441k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- PleatFolding_GC (Algorithmic Folding Complexity)
- PleatFolding_JCCGG2009 (Algorithmic Folding Complexity)

See also other papers by Erik Demaine.

Last updated December 29, 2018 by Erik Demaine.