Algorithmic folding complexity

Cardinal, Jean ; Demaine, Erik D. ; Demaine, Martin L. ; Imahori, Shinji ; Langerman, Stefan ; Uehara, Ryuhei

Springer

Others  :  http://dspace.mit.edu/openaccess-disseminate/1721.1/62218

美国|英语

来源: MIT Theses in DSpace@MIT

【 摘 要 】

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.