Paper by Erik D. Demaine

Reference:

Jean Cardinal, Erik D. Demaine, Martin L. Demaine, Shinji Imahori, Stefan Langerman, and Ryuhei Uehara, “Algorithmic Folding Complexity”, in Proceedings of the 20th Annual International Symposium on Algorithms and Computation (ISAAC 2009), Lecture Notes in Computer Science, volume 5878, Hawaii, USA, December 16–18, 2009, pages 452–461.

BibTeX

@InProceedings{PleatFolding_ISAAC2009,
  AUTHOR        = {Jean Cardinal and Erik D. Demaine and Martin L. Demaine and
                   Shinji Imahori and Stefan Langerman and Ryuhei Uehara},
  TITLE         = {Algorithmic Folding Complexity},
  BOOKTITLE     = {Proceedings of the 20th Annual International Symposium on
                   Algorithms and Computation (ISAAC 2009)},
  bookurl       = {http://theory.utdallas.edu/ISAAC2009/},
  SERIES        = {Lecture Notes in Computer Science},
  seriesurl     = {http://www.springer.de/comp/lncs/},
  VOLUME        = 5878,
  ADDRESS       = {Hawaii, USA},
  MONTH         = {December 16--18},
  YEAR          = 2009,
  PAGES         = {452--461},

  doi           = {https://dx.doi.org/10.1007/978-3-642-10631-6_47},
  dblp          = {https://dblp.org/rec/conf/isaac/CardinalDDILU09},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1007/978-3-642-10631-6_47">SpringerLink</A>.},
  replaces      = {PleatFolding_JCCGG2009},
  papers        = {PleatFolding_GC; PleatFolding_JCCGG2009},
}

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/lg n), meeting a previously known lower bound.

Comments:

This paper is also available from SpringerLink.

Availability:

The paper is available in PDF (441k).

See information on file formats.

[Google Scholar search]

Related papers:

PleatFolding_GC (Algorithmic Folding Complexity)

PleatFolding_JCCGG2009 (Algorithmic Folding Complexity)