6.885: Geometric Folding Algorithms: Linkages, Origami, Polyhedra (Fall 2007)

Prof. Erik Demaine       TA: Nadia Benbernou


[Home] [Problem Sets] [Project] [Lecture Notes] [Problem Session Notes]
Linkages:

Paper:

Polyhedra:

Overview

Geometric folding offers a wealth of beautiful geometric and algorithmic problems. Recent results in this area have led, for example, to powerful techniques for complex origami design. Other problems relate to how to fold robotic arms without collision, how to bend sheet metal into desired 3D shapes, and understanding how proteins fold. Despite much recent progress on folding problems, some of the most fundamental questions remain tantalizingly unsolved. This class covers the state-of-the-art in folding research, including a variety of open problems, enabling the student to do research and advance the field.

We will also organize an optional problem-solving session, during which we can jointly try to solve open problems in folding. Results from this session would likely lead to class projects, and hopefully also paper submissions, but this is not the only way to do a class project. Class projects can also take the form of well-written descriptions of one or more papers in the area; formulations of clean, new open problems; implementations of existing algorithms; or folding-inspired sculptures. Projects can be purely mathematical (geometric) and/or theoretical computer science (algorithmic/complexity theoretic) and/or artistic. Students are also required to do a small number of problem sets and a project presentation.

Topics

This is an advanced class on computational geometry focusing on folding and unfolding of geometric structures including linkages, proteins, paper, and polyhedra. Examples of problems considered in this field: Many folding problems have applications in areas including manufacturing, robotics, graphics, and protein folding. This class covers many of the results that have been proved in the past few years, as well as the several exciting open problems that remain open.

Textbook

The textbook for the class is the recently completed Geometric Folding Algorithms: Linkages, Origami, Polyhedra by Erik Demaine and Joseph O'Rourke, published by Cambridge University Press (2007). The list price is $95. Quantum Books offers a sale price of $76. A further reduced price is available as part of a bulk class purchase; let Erik know if you want to be part of it.

Additional recommended reading is Origami Design Secrets: Mathematical Methods for an Ancient Art by Robert Lang.

Specifics

Lecture Time: Mondays and Wednesdays at 11:00am–12:30pm
Lecture Room: MIT room 2-139
First Lecture: Wednesday, September 5, 2007
Problem Session Time: Tuesdays at 6:00pm-9:00pm
Problem Session Room: 2-143
Professor: Erik Demaine, 32-G680
TA: Nadia Benbernou, 32-G694
Problem Session
   Co-organizer:
Timothy Abbott
Units: 3-0-9
Prerequisites: 6.046 or equivalent background in discrete mathematics and algorithms
Credit: H-level and EC-level credit; no ED credit
Requirements: Written project and project presentation. Small number of problem sets.

Participating

We welcome both undergraduate and graduate students from all universities, although officially this is a graduate class.

Previous Offerings

This class was offered once before, in Fall 2004. You might be interested in the lecture notes, problem sets, etc. from that offering.