6.885: Folding and Unfolding in Computational Geometry (Fall 2004)
[Problem session notes]
The main requirement for this class,
other than problem sets,
is the project. The project consists of two components that will
be "turned in":
Projects can take many different forms.
Here are the five main general categories:
- A paper describing what you did.
This should be a well-written document describing the problem
you tackled (be it an implementation, mathematical, or artistic
challenge), what approaches you took, what difficulties you encountered,
and what results you found, in addition to citing the relevant literature.
Aim for on the order of 10 pages, say in the range 5–20 pages.
- A presentation describing what you did
(or how far you've gotten at the time of presentation).
For slides, I will assume that you will be using a data projector
(showing PDF, PostScript, PowerPoint, or your own programs).
You can either send me the files ahead of time to use my laptop,
or use your own laptop.
(The latter is encouraged if you are running your own programs.)
If you need other technology, let me know.
Pure blackboard presentations are discouraged except for the experienced.
The exact length is to be determined, but the presentations
will be during normal lecture time.
Several specific project ideas are listed in the
handwritten lecture notes under the
(The latter heading is used for projects of the last type.)
You are encouraged to look through these ideas
(and the lecture notes in general) for inspiration.
- Implement an algorithm, an illustration of a result, or
a tool for experimenting with a problem.
Typically, a good format for such an implementation is an applet
(written in Java or
but other environments are fine too.
- Design and create a sculpture that uses ideas from this class.
Such a sculpture should be both artistically compelling and
technically grounded (though the latter need not be explicitly visible).
The sculpture can be physical or virtual, though in the latter case
the standards will be higher because of the reduced challenge.
(One way to compensate is to make several virtual sculptures,
e.g., connected in a theme.)
Sculpture is to be loosely interpreted, e.g., you could make several
aesthetic models illustrating a particular algorithm like folding
and one straight cut.
- Pose an open problem (or collection of related open problems).
You might pose open problems related to another field of research
with which you are familiar, or pose something that comes to you out of
Ideally you should think about solving the problem, or how it relates
to other problems.
- Survey a collection of 2 or 3 or more related papers.
Ideally you should avoid overlap with the textbook,
Folding and Unfolding in
- Try to solve an open problem.
This is the most ambitious kind of project, so the expectations in terms
of results are correspondingly lower. What is important is to describe
a clear problem, take (at least) one good approach to that problem, and
describe to what extent it worked or did not work. You should not feel
pressure in terms of grades to produce results, but you should spend
time thinking and trying to solve the problem. (In particular, if you
succeed, you/we can write a research paper and try to publish it.)
Collaboration is particularly encouraged for projects of this type,
as is participation in the open-problem solving session.
No matter what you choose, project proposals must be approved by me.
You should do this as soon as possible, and no later than
Monday, November 1, 2004.
Project proposals are due Monday, November 1, 2004.
By MIT policy, the paper is due on the last regularly scheduled lecture
of this class, Wednesday, December 8, 2004.
The presentation is due somewhat earlier depending on when it gets scheduled
into a lecture slot; if your presentation is earlier, you are expected to have
made less progress, but you should still give a clear description of the
problem you are tackling and what you plan to do.
Collaboration is strongly encouraged, especially for research projects--this
is often the key to successful research in theoretical computer science.
You can work in a small group of students in the class if you find common
interests. (Keep in mind that students listening to the class will have
less time to devote, but they are welcome to participate in a project too.)
You are also welcome to collaborate with anyone outside the class,
including your research supervisor (if you have one) and including me.
The only constraint for the class is that your own contribution should be
substantial enough, both in terms of solving problems and writing it up.
To evaluate "substantial enough", you should talk to me.
In any case, you should tell me who you are working with as the collaborations
arise (i.e., before you turn in your project paper). Collaborations should
also be clearly marked on the paper and presentation slides.
As students choose projects, their titles will be listed here, to avoid
overlap, and facilitate the possibility of collaboration. Please let me know
if there are any inaccuracies (unlisted projects or mislisted projects).
- Timothy Abbott and Reid Barton — Extensions and improvements to Kempe's Universality Theorem
- Michael Baym — Interlocked 3D linkages
- Michael Burr — Finiteness of pops
- Blaise Gassend — Limit definitions of semifree folding, and topological proof of infinitesimal carpenter's rule theorem
- Benjamin Hebert — Faster algorithms for testing generic rigidity
- Hank Hoffmann — 3D linkage unfolding using energy
- Ariel Rideout and Ryan Williams — Implementation of straight-skeleton fold-and-cut algorithm
- Toby Schachman — Box pleating
- Steven Sivek — 2-by-n map folding
- Paul Stellman and Satoshi Takahashi — Energy unfolding of Single-vertex origami with applications to nano-origami