Paper by Erik D. Demaine

Reference:

Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Joseph S. B. Mitchell, Saurabh Sethia, and Steven S. Skiena, “When Can You Fold a Map?”, Computational Geometry: Theory and Applications, volume 29, number 1, September 2004, pages 23–46. Special issue of selected papers from the 10th Annual Fall Workshop on Computational Geometry, 2000.

BibTeX

@Article{MapFolding,
  AUTHOR        = {Esther M. Arkin and Michael A. Bender and Erik D. Demaine
                   and Martin L. Demaine and Joseph S. B. Mitchell and
                   Saurabh Sethia and Steven S. Skiena},
  TITLE         = {When Can You Fold a Map?},
  JOURNAL       = {Computational Geometry: Theory and Applications},
  journalurl    = {https://www.sciencedirect.com/journal/computational-geometry},
  VOLUME        = 29,
  NUMBER        = 1,
  MONTH         = {September},
  YEAR          = 2004,
  PAGES         = {23--46},
  NOTE          = {Special issue of selected papers from the 10th Annual Fall
                   Workshop on Computational Geometry, 2000.},

  length        = {24 pages},
  doi           = {https://dx.doi.org/10.1016/J.COMGEO.2004.03.012},
  dblp          = {https://dblp.org/rec/journals/comgeo/ArkinBDDMSS04},
  comments      = {This paper is also available from
                   <A HREF="http://dx.doi.org/10.1016/j.comgeo.2004.03.012">ScienceDirect</A>,
                   and as
                   <A HREF="http://arXiv.org/abs/cs.CG/0011026">
                   arXiv:cs.CG/0011026</A> of the
                   <A HREF="http://arXiv.org/archive/cs/intro.html">
                   Computing Research Repository (CoRR)</A>.},
  PAPERS        = {MapFolding_CGW2014; MapFoldingWADS2001; CGW2000},
  UPDATES       = {Ivars Peterson wrote an article describing these results,
                   &ldquo;Proof clarifies a map-folding problem&rdquo;,
                   <I><A HREF="http://www.sciencenews.org/">Science
                   News</A></I> 158(26-27):406, December 23-30, 2002.
                   <P>
                   Helen Pearson also wrote an article describing these
                   results,
                   &ldquo;<A HREF="http://www.nature.com/nsu/020218/020218-1.html">Origami
                   solves road map riddle</A>&rdquo;,
                   <I><A HREF="http://www.nature.com/nsu/">Nature Science
                   Update</A></I>, February 18, 2002.},
  replaces      = {MapFoldingWADS2001; CGW2000},
}

Abstract:

We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple folds? There are several models of simple folds; the simplest one-layer simple fold rotates a portion of paper about a crease in the paper by ±180°. We first consider the analogous questions in one dimension lower—bending a segment into a flat object—which lead to interesting problems on strings. We develop efficient algorithms for the recognition of simply foldable 1D crease patterns, and reconstruction of a sequence of simple folds. Indeed, we prove that a 1D crease pattern is flat-foldable by any means precisely if it is by a sequence of one-layer simple folds.

Next we explore simple foldability in two dimensions, and find a surprising contrast: “map” folding and variants are polynomial, but slight generalizations are NP-complete. Specifically, we develop a linear-time algorithm for deciding foldability of an orthogonal crease pattern on a rectangular piece of paper, and prove that it is (weakly) NP-complete to decide foldability of (1) an orthogonal crease pattern on a orthogonal piece of paper, (2) a crease pattern of axis-parallel and diagonal (45-degree) creases on a square piece of paper, and (3) crease patterns without a mountain/valley assignment.

Comments:

This paper is also available from ScienceDirect, and as arXiv:cs.CG/0011026 of the Computing Research Repository (CoRR).

Updates:

Ivars Peterson wrote an article describing these results, “Proof clarifies a map-folding problem”, Science News 158(26-27):406, December 23-30, 2002.

Helen Pearson also wrote an article describing these results, “Origami solves road map riddle”, Nature Science Update, February 18, 2002.

Length:

The paper is 24 pages.

Availability:

The paper is available in PostScript (608k), gzipped PostScript (226k), and PDF (281k).

See information on file formats.

[Google Scholar search]

Related papers:

MapFolding_CGW2014 (Simple Folding is Strongly NP-Complete)

MapFoldingWADS2001 (When Can You Fold a Map?)

CGW2000 (When Can You Fold a Map?)