Paper by Erik D. Demaine

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² n). We also show that a lower bound of the complexity of the problems is Ω(lg² 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)