When Can You Fold a Map?
<|reference_start|>When Can You Fold a Map?: 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 degrees. 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.<|reference_end|>
@article{arkin2000when,
    title={When Can You Fold a Map?},
    author={Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L.
  Demaine, Joseph S. B. Mitchell, Saurabh Sethia, Steven S. Skiena},
    journal={arXiv preprint arXiv:cs/0011026},
    year={2000},
    archivePrefix={arXiv},
    eprint={cs/0011026},
    primaryClass={cs.CG cs.DM}
}