Paper by Erik D. Demaine
- 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.
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.
- The paper is 2 pages.
- 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.
These pages are generated automagically from a
Last updated April 22, 2019 by