Ivars Peterson's MathTrek

January 15, 2001

# Folding Maps

Anyone trying to refold an opened road map is wrestling with the same sort of challenges confronted by origami designers and sheet metal benders.

The problem of returning a creased sheet to its neatly folded state gets tougher when you're not sure if the sheet can be folded into a flat packet and when you're not permitted to change the crease directions. Such conundrums can arise, for example, when designers specify how to bend sheet metal to produce, say, car doors, airplane parts, or heating ducts.

Now, Erik D. Demaine of the computer science department at the University of Waterloo in Ontario and his coworkers have developed an efficient method for recognizing when a creased sheet indeed is foldable into a flat package. The researchers report their results in an unpublished paper available at http://xxx.lanl.gov/abs/cs.CG/0011026.

"This represents an initial step toward developing an understanding of the three-dimensional, sheet-metal-folding problem," says applied mathematician Joseph S.B. Mitchell of the State University of New York at Stony Brook. "We need better mathematical tools for dealing with problems in going from a design to a manufactured part."

Demaine and his collaborators started with the one-dimensional case of the folding problem: When is it possible to refold a line segment, which had been creased upward to form mountain creases and downward to form valley creases, into a compact configuration resembling the cross section of a neatly folded map?

The researchers focused on recognizing flat-folding crease patterns that arise as the result of so-called simple foldings. "In this model, a flat folding is made by a sequence of simple folds, each of which folds one or more layers of paper along a single line segment," they remark.

The researchers discovered that certain mixes of two configurations--a zigzag fold, called a crimp, and a doubled-back fold, or hem--permit a creased segment to be folded into a flat profile. This finding enabled the researchers to develop criteria and an efficient algorithm for recognizing a one-dimensional crease pattern that can be folded flat.

"The two-dimensional case is more complicated," Demaine says. However, if a rectangular sheet is creased only along vertical and horizontal lines to form a grid, it's possible to analyze the resulting mountain-valley crease pattern in terms of the criteria developed for the one-dimensional case. As a result, there's an efficient method for deciding whether a creased sheet can fold flat. Adding complications, such as diagonal creases, makes solving the problem considerably more time-consuming, Demaine notes.

Demaine's interest in foldability arose out of his hobby, origami. Mathematicians and others have been studying ways to systematize origami design by developing rules that would enable a computer to calculate what sequence of creases in a square a paper will produce a desired figure. Important to this task is a determination from a crease pattern whether the resulting three-dimensional figure can collapse neatly into a flat form, as required in traditional origami.

Beyond the mathematics of origami, "our study is motivated by applications in sheet metal and paper product manufacturing, where one is interested in determining if a given structure can be manufactured using a specified creasing machine, which is typically restricted to performing simple folds," the researchers note.

"While origamists can develop particular skill in performing non-simple folds to make beautiful artwork, practical problems of manufacturing sheet goods require simple and constrained folding operations," they add. "Our goal is to develop a first suite of results that may be helpful towards a fuller understanding of the several manufacturing problems that arise, for example, in making three-dimensional cardboard and sheet-metal structures."

Demaine says his work has also yielded insights into refolding road maps. One trick is to start with the fold that serves as a border between sequences of mountain and valley creases that mirror each other on either side of the border.

Whether anyone would have the patience to do such a careful analysis while in the throes of a refolding adventure is another matter, however. The whole business calls to mind the old saw: The easiest way to refold a road map is differently.

References:

Arkin, E.M., et al. Preprint. When can you fold a map? Available at http://xxx.lanl.gov/abs/cs.CG/0011026.

Gardner, M. 1983. The combinatorics of paper folding. In Wheels, Life and Other Mathematical Amusements. New York: W.H. Freeman.

Peterson, I. 2000. Proof clarifies a map-folding problem. Science News 158(Dec. 23&30):406.

______. 2000. Unlocking puzzling polygons. Science News 158(Sept. 23):200. Available at http://www.sciencenews.org/20000923/bob1.asp.

______. 1995. Paper folds, creases, and theorems. Science News 147(Dec. 2):44.

Information about research on computer-aided design and three-dimensional sheet-metal folding can be found at http://www.ri.cmu.edu/projects/project_41.html.

Erik Demaine has a Web page at http://daisy.uwaterloo.ca/~eddemain/.

The 3rd International Meeting of Origami Science, Math, and Education, to be held March 9-11, 2001, at Asilomar, Calif., has a Web site at http://www.ifold.org/ and a Web page at http://web.merrimack.edu/~thull/osm/osm.html

Ivars Peterson is the mathematics/computer writer and online editor at Science News (http://www.sciencenews.org). He is the author of The Mathematical Tourist, Islands of Truth, Newton's Clock, Fatal Defect, and The Jungles of Randomness. He also writes for the children's magazine Muse (http://www.musemag.com) and is working on a book about math and art.

NEW! NEW! NEW!

Math Trek 2: A Mathematical Space Odyssey by Ivars Peterson and Nancy Henderson. For children ages 10 and up. New York: Wiley, 2001. ISBN 0-471-31571-0. \$12.95 USA (paper).