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]
[Accessibility]
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:
- What forms of origami can be designed automatically by algorithms?
- What shapes can result by folding a piece of paper flat and
making one complete straight cut?
- What polyhedra can be cut along their surface and unfolded into a flat
piece of paper without overlap?
- When can a linkage of rigid bars be untangled or folded into a
desired configuration?
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.
