Quiz: What Waterloo graduate was hired at
the tender age of 21 to become the all-time youngest professor at the
Massachusetts Institute of Technology? That same former graduate student
now has over 100 publications to his credit and sits on the organizing
committee for some seven workshops and symposia. Although they seem like
the accompishments of a much older member of faculty, Waterloo's Erik
Demaine was hired at MIT just last year.
His supervisors in the School of computer Science, Anna Lubiw and Ian Munro, are justly proud of him. One of his many interests is an arcane corner of computational geometry that seeks to fold polygons into polyhedra and, conversely, to cut polyhedra into polygons, could be called computational origami. Demaine is very good at it. A glance at his website shows that his interests range far beyond computational origami. Demaine is good at many things.
Quiz: How much schooling did Demaine receive as a lad? If you said that he must have gone to one of those fancy, high-powered prep schools or to an intensive university experimental school, you'd be wrong. Demaine didn't go to school at all. Instead, he was taught at home by his father, a craftsman and amateur mathematician. At the age of 12 Demaine succeeded in convincing the authorities at Dalhousie University in his home town of Halifax to admit him. Two years later, in 1995, he had completed his under-graduate work at Dalhousie and had moved to Waterloo, where he finished his Master's degree under David Taylor. He completed his PhD in 2001.
The key to Demaine's success is surely his enjoyment of mathematics and computing. According to Anna Lubiw, one of his supervisors, "Erik loves mathematics. He turns everything he does into math problems. What would happen if you juggled balls with strings attached to them? What patterns appear when you squash a cardboard box? What kind of folds would you make on a polyhedron?" His thesis under Lubiw focused on a problem called The Carpenter's Rule. You may have seen them, popular before tape measures became common; a set of segments that are hinged at their ends may be unfolded from a compact, stacked arrangement into a straight line. Markings on the edge (irrelevant for Erik's problem) yield the measurements.
Problem: Given such a carpenter's rule in a "simple" state (no segment crosses or touches another) can you open it by steps to a straight line so that the configuration remains simple throughout the procedure?
The problem is not exactly trivial, although solutions are easy to find for many initial states.
Other configurations, such as the one in the figure above, are not so easy. Demaine adopted the notion of "expansive motions," changes in one or more angles that not only preserve the condition of simplicity, but result in at least one pair of vertices (hinges) being further apart, while no other pairs get closer together. It is easy to prove that a series of expansive motions will eventually result in a straightened carpenter's rule, but it's very hard to prove that such motions can always be found. But Demaine proved it, working jointly with mathematicians Robert Connelly ofCornell and Günther Rote of the Free University of Berlin.
"It's a sexy problem," said Demaine recently in his office at MIT. "It's a very attractive problem because it's very simple to state. And yet it was very hard to solve. The problem goes back about 25 years and dozens of people had worked on it, though no one could solve it."
Even while working on his MSc and PhD degrees at the University of Waterloo, Erik worked on many other problems, usually with one or more faculty members, not to mention mathematicians and computer scientists from other institutions.
Not to mention his father, Marty Demaine. Marty is not only a skilled glassblower and stained glass craftsman, he is an amateur mathematician in the best sense of the word.
Even before completing his Master's Erik had begun collaborative work with Anna Lubiw and Marty. One problem that attracted all three parties could be called fold-and-cut origami. In its most general form, you are given a polygon on a sheet of paper. Next, you are asked to fold the paper in such a way that a single, straight cut with a pair of scissors (or paper cutter) suffices to separate the polygon from the paper. The single cut, in other words, follows all the lines of the polygon simultaneously. Here's a simple version of the problem that you may try at home.
Puzzle: Draw a triangle on a flat sheet of paper, then (somehow) fold the paper so that with one straight cut the triangle emerges from the paper. What remains, by the way, should have no cuts in it at all. For maximum difficulty the triangle should be scalene, with no two sides equal.
If this puzzle baffles you, look up the solution in Archimedes Sandbox, a Mathematics Faculty web feature. Jim Akiyama, a math popularizer and puzzle expert with rock-star status in Japan, demonstrated the solution on one of his nationwide TV shows.
Demaine also solved the so-called Fold and Cut problem in its most general form while at the University of waterloo. With two major problems solved before he obtained his PhD, it's no wonder that Erik was awarded the prestigious NSERC (National Science and Engineering Research Council) 2003 Doctoral Prize. Currently, he has extended the problem into the practical realm by investigating what shapes can be manufactured from a single piece of sheet metal.
Erik also worked on data structures problems with Ian Munro and, even while working on his PhD, produced many joint papers with people such as Joseph Mitchell of Stoneybrook and Joseph O'Rourke of Smith College, both senior researchers in computational geometry. And now, in the year 2003, he has over 100 papers that include 96 collaborators.
Demaine became a keen collaborator, according to Lubiw, as a direct result of the home schooling environment of his early youth. Not only did he become used to working with others early, the experience sharpened his skills at presenting material orally and in writing.
"I learned a lot from talking to people. My father always stressed communications skills and that served me well in academia. I'm not shy about approaching people to test out ideas. In fact, when I take on a big problem, that's the first thing I do."
Demaine currently busies himself in an astonishing range of research areas, including discrete and computational geometry, advanced data structures, computational complexity, approximation algorithms, distributed systems, and game theory.
He is currently an Assistant Professor in Electrical Engineering and Computer Science at the Massachusetts Institute of Technology, as well as a member of the Theory of Computation Group in the Laboratory for Computer Science.
Despite all his success and the pressure that inevitably brings, Erik "remains outwardly calm and acts like nothing is wrong, even with deadlines looming," says Lubiw. Perhaps that's because his universe is unfolding as it should.
March 2003
David R. Cheriton School of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1
Tel: 519-888-4567 x33293
Fax: 519-885-1208
Contact | Feedback: cs-webmaster@cs.uwaterloo.ca | David R. Cheriton School of Computer Science | Faculty of Mathematics
Last modified: Monday, 11-Sep-2006 14:06:32 EDT
