Computer Science – Computational Geometry
Scientific paper
2000-11-20
Computer Science
Computational Geometry
24 pages, 19 figures. Version 3 includes several improvements thanks to referees, including formal definitions of simple folds
Scientific paper
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.
Arkin Esther M.
Bender Michael A.
Demaine Erik D.
Demaine Martin L.
Mitchell Joseph S. B.
No associations
LandOfFree
When Can You Fold a Map? does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with When Can You Fold a Map?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and When Can You Fold a Map? will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-573577