Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Martin L. Demaine, Goran Konjevod, and Robert J. Lang, “Folding a Better Checkerboard”, 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 1074–1083.

BibTeX

@InProceedings{Checkerboard_ISAAC2009,
  AUTHOR        = {Erik D. Demaine and Martin L. Demaine and Goran Konjevod
                   and Robert J. Lang},
  TITLE         = {Folding a Better Checkerboard},
  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         = {1074--1083},

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

Abstract:

Folding an n × n checkerboard pattern from a square of paper that is white on one side and black on the other has been thought for several years to require a paper square of semiperimeter n². Indeed, within a restricted class of foldings that match all previous origami models of this flavor, one can prove a lower bound of n² (though a matching upper bound was not known). We show how to break through this barrier and fold an n × n checkerboard from a paper square of semiperimeter ½ n² + O(n). In particular, our construction strictly beats semiperimeter n² for (even) n > 16, and for n = 8, we improve on the best seamless folding.

Comments:

This paper is also available from SpringerLink.

Availability:

The paper is available in PostScript (587k), gzipped PostScript (192k), and PDF (153k).

See information on file formats.

[Google Scholar search]