Algorithmic Folding Complexity
by Stefan Langerman
Université Libre de Bruxelles 

Time: 2PM am on Thursday, Dec 17, 2009
Venue: 3464

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
discuss the maximum possible folding complexity of an arbitrary string
of length n.
Joint work with Jean Cardinal, Erik D. Demaine, Martin L. Demaine,
Shinji Imahori, and Ryuhei Uehara.