When Can You Fold a Map?
| dc.creator | Arkin, Esther M. | |
| dc.creator | Bender, Michael A. | |
| dc.creator | Demaine, Erik D. | |
| dc.creator | Demaine, Martin L. | |
| dc.creator | Mitchell, Joseph S. B. | |
| dc.creator | Sethia, Saurabh | |
| dc.creator | Skiena, Steven S. | |
| dc.date | 2000-11-20 | |
| dc.date | 2003-08-31 | |
| dc.date.accessioned | 2026-07-07T03:16:44Z | |
| dc.date.available | 2026-07-07T03:16:44Z | |
| dc.description | 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. | |
| dc.description | 24 pages, 19 figures. Version 3 includes several improvements thanks to referees, including formal definitions of simple folds, more figures, table summarizing results, new open problems, and additional references | |
| dc.identifier | https://arxiv.org/abs/cs/0011026 | |
| dc.identifier | http://arxiv.org/abs/cs/0011026 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/30465 | |
| dc.subject | Computational Geometry | |
| dc.subject | Discrete Mathematics | |
| dc.subject | F.2.2; G.2.1 | |
| dc.title | When Can You Fold a Map? | |
| dc.type | text |