6.885: Folding and Unfolding in Computational Geometry (Fall 2004)
[Home]
[Problem Sets]
[Project]
[Erik's notes]
[Problem session notes]
[Email archive]
[Accessibility]
Linkages:
Paper:
Polyhedra:
Overview
Folding offers a wealth of beautiful geometric and algorithmic problems.
Recent results in this area have lead, 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 protein folding. 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. The class includes guest lectures from visiting experts.
I 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; or implementations of existing
algorithms. Projects can be purely mathematical (geometric) and/or
theoretical computer science (algorithmic/complexity theoretic).
Students are also required to do a small number of problem sets,
and possibly 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 a draft of the book
Folding and Unfolding in Computational Geometry (FUCG)
by Erik Demaine and
Joseph O'Rourke.
Additional recommended reading is
Origami Design
Secrets: Mathematical Methods for an Ancient Art
by Robert Lang.
A copy of this book is on reserve in the
CSAIL Reading Room.
Specifics
Lecture Time:
Mondays and Wednesdays at 11:00am-12:30pm
Lecture Room:
4-231
First Lecture:
Wednesday, September 8, 2004
Problem Session Time:
Thursdays at 6:00pm-8:00pm
Problem Session Room:
2-147
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 possibly project presentation.
Small number of problem sets.
Participating
This is a graduate class but both undergraduate and graduate students are
welcome.
If you are interested in attending the class (for credit or as a listener),
send me email
to join the mailing list for class information.
Further details will also be posted on this webpage.