Algorithmic Folding Complexity

作者：Cardinal Jean^*; Demaine Erik D; Demaine Martin L; Imahori Shinji; Ito Tsuyoshi; Kiyomi Masashi; Langerman Stefan; Uehara Ryuhei; Uno Takeaki

来源：Graphs and Combinatorics, 2011, 27(3): 341-351.

DOI：10.1007/s00373-011-1019-0

• Algorithm design
• Origami

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(2) n). We also show that a lower bound of the complexity of the problems is Omega(lg(2) n/lg lg n). Next we show that almost all mountain-valley patterns require Omega(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.

• 出版日期2011-5