401. Algorithmic folding complexity
- Author
-
Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science, Demaine, Erik D., Demaine, Martin L., Cardinal, Jean, Imahori, Shinji, Langerman, Stefan, Uehara, Ryuhei, Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science, Demaine, Erik D., Demaine, Martin L., Cardinal, Jean, Imahori, Shinji, Langerman, Stefan, and Uehara, Ryuhei
- 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/lgn), meeting a previously known lower bound.
- Published
- 2011