# 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 arise, for example, when designers determine 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 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 into mountain creases and downward into 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.

There are different types of simple folds, depending on how many layers of paper are required or allowed to be folded along a crease. At the same time, it is also possible to fold a sheet of paper into a flat configuration using other types of folds; for example, in creating the classic origami crane.

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.

“In addition to its inherent interest in 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. 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. That calls to mind the old saw: The easiest way to refold a road map is differently.