Paper by Erik D. Demaine
- 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.
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(lg2 n). We
also show that a lower bound of the complexity of the problems is
Ω(lg2 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
- This paper is also available from SpringerLink.
- 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.
These pages are generated automagically from a
Last updated April 15, 2018 by