Proof clarifies a map-folding problem

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 or heating ducts.

Now, Erik D. Demaine of 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 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 in mountain creases and downward in valley creases, into a compact configuration resembling the cross section of a neatly folded map?

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 of paper will produce a desired figure (SN: 1/21/95, p. 44). Important to this task is a determination from a crease pattern of whether the resulting three-dimensional figure can collapse neatly into a flat form, as required in traditional origami.

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.