News of the Week

Shapeshifting Made Easy

Science  05 Sep 2008:
Vol. 321, Issue 5894, pp. 1282a
DOI: 10.1126/science.321.5894.1282a

MATHFEST 2008, 31 JULY-2 AUGUST, MADISON, WISCONSIN

Mathematicians aren't squeamish about doing dissections, but they do often come unhinged. Now computational geometers at the Massachusetts Institute of Technology (MIT) in Cambridge have proven it's possible to do mathematical dissections without falling to pieces.

The victims in this case are not frogs but polygons: simple geometric shapes bounded by straight sides. In the early 19th century, mathematicians proved that any two polygons with the same area can be cut into a finite number of matching pieces. For example, it's possible to cut a square into four pieces and rearrange them into an equilateral triangle.

Location, location, location.

A square can become an equilateral triangle without ever falling apart (top). The same is true for other pairs of polygons. The proof starts with a trick that, in effect, moves hinges around (bottom).

CREDIT: E. DEMAINE ET AL.

About 100 years ago, the English mathematician and puzzle designer Henry Dudeney added an extra wrinkle to the dissection challenge: He showed that the rearrangement from square to equilateral triangle can be done with pieces connected by hinges (see figure, above). Dissection enthusiasts have since devised many more hinged transformations.

In 1997, Greg Frederickson, a computer scientist and geometric-dissection buff at Purdue University in West Lafayette, Indiana, asked whether what Dudeney did for the square and triangle can be done for any two polygons. The question caught the attention of Erik Demaine, then beginning graduate work in computer science. A decade later, Demaine, now a professor at MIT, has the answer: in a word, yes.

Demaine returned to Frederickson's problem last fall with his father, Martin Demaine, and four students in a problem-solving seminar: Timothy Abbott of MIT, Zachary Abel and Scott Kominers of Harvard University, and David Charlton of Boston University. The group came up with a general procedure for turning an arbitrary dissection into a hinged dissection. Demaine described their proof at MathFest. “It was a surprising result to me, because I thought it was false,” he says.

Their proof starts with an idea “so crazy that we never thought of it,” Demaine says. That idea is simply to take an unhinged dissection of one polygon and arbitrarily add hinges, then subdivide the pieces and add additional hinges until the polygon can contort into its equal-area partner. The key step is to show that judicious subdivision can, in effect, take a hinge that connects, say, piece A to piece B and move it to connect A to C (see figure).

“The movement is magical,” Frederickson says. On the other hand, he notes, “you don't get very pretty dissections this way.”

The construction works on three-dimensional (3D) dissections as well, which could help guide the design of reconfigurable robots—modular machines that rearrange their parts like real-life Transformers. In 3D, unfortunately, equal volume doesn't guarantee the existence of a dissection. But when dissections do exist, the MIT group's construction shows that they can be refined into hinged dissections. The results are an encouraging first step toward applications, Demaine says: “Now the optimization begins.”

Navigate This Article