Erik Demaine Massachusetts Institute of Technology Date and time: Wed, 04/11/2007 - 3:30pm Physics Building, Room 202 Cantrell Lectures Wednesday, April 11, 2007 3:30 p.m. Physics Bldg., Room 202 Title of talk: Origami, Linkages, and Polyhedra: Folding with Algorithms Abstract: What forms of origami can be designed automatically by a computer? What shapes can result by folding a piece of paper flat and making one complete straight cut? What 3D surfaces can be cut open and unfolded into a flat piece of paper without overlap? When can a robot arm or protein be untangled or folded into a desired configuration? Geometric folding and unfolding is a branch of discrete and computational geometry that addresses these and many other intriguing questions. I will give a taste of the many discoveries that have been made in the past few years, as well as the several exciting problems that remain unsolved. Folding problems have applications throughout science and engineering, for example, to safer automobiles, space deployment, manufacturing, robotics, computer graphics, and protein folding. Thursday, April 12, 2007 3:30p.m., Boyd Graduate Studies, Room 328 Title of talk: Mathematics Meets Art, Puzzles, and Magic: Fun with Algorithms Abstract: Solving and designing puzzles, creating sculpture and architecture, and inventing magic tricks all lead to fun and interesting algorithmic problems. I will describe some of our explorations into these areas (together with my father, Martin Demaine, and several others). PUZZLES. Solving a puzzle is like solving a research problem. Both require the right cleverness to see the problem from the right angle, and then explore that idea until you find a solution. The main difference is that the puzzle poser usually guarantees that the puzzle is solvable. Puzzles also lead to the meta-puzzle of how to design algorithms that themselves can design families of puzzles. ART. Elegant algorithms are beautiful. A special treat is when that beauty translates visually. Sometimes this is by design, when you develop an algorithm to compose artwork within a particular family. Other times the visual beauty of an algorithm just appears, without anticipation. MAGIC. Mathematics is the basis for many magic tricks, particularly “self-working” tricks. One of the key people at the intersection of mathematics and magic is Martin Gardner, whose work has inspired several of the results described in this talk. Algorithmically, our goal is to automatically design families of magic tricks. Friday, April 13, 2007 3:30p.m., Boyd Graduate Studies, Room 328 Title of talk: Linkage Folding: From Erdos to Proteins Abstract: Linkages have a long history ranging back to the 18th century in the quest for mechanical conversion between circular motion and linear motion, as needed in a steam engine. In 1877, Kempe wrote an entire book of such mechanisms for "drawing a straight line". (In mathematical circles, Kempe is famous for an attempted proof of the Four-Color Theorem, whose main ideas persist in the current, correct proofs.) Kempe designed many linkages which, after solidification by modern mathematicians Kapovich, Millson, and Thurston, establish an impressively strong result: there is a linkage that signs your name by simply turning a crank. Over the years mathematicians, and more recently computer scientists, have revealed a deep mathematical and computational structure in linkages, and how they can fold from one configuration to another. In 1936, Erdos posed one of the first such problems (now solved): does repeatedly flipping a pocket of the convex hull convexify a polygon after a finite number of flips? This problem by itself has an intriguingly long and active history; most recently, in 2006, we discovered that the main solution to this problem, from 1939, is in fact wrong.