**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?”, in
*Proceedings of the 7th Workshop on Algorithms and Data Structures (WADS 2001)*, Lecture Notes in Computer Science, volume 2125, Providence, Rhode Island, August 8–10, 2001, pages 401–413. **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 1-D crease patterns, and reconstruction of a sequence of simple folds. Indeed, we prove that a 1-D 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 the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/2125/21250401.pdf.
**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. **Copyright**:- The paper is \copyright Springer-Verlag.
**Length**:- The paper is 12 pages.
**Availability**:- The paper is available in PostScript (145k) and gzipped PostScript (47k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- MapFolding_CGW2014 (Simple Folding is Strongly NP-Complete)
- MapFolding (When Can You Fold a Map?)
- CGW2000 (When Can You Fold a Map?)

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.