Erik Demaine's
Folding and Unfolding Page
Folding and unfolding is an exciting area of geometry. It is
attractive in the way that problems and even results can be easily understood,
with little knowledge of mathematics or computer science, yet the solutions are
difficult and involve many sophisticated techniques. The general sort of
problem considered is how a particular object (e.g., linkage, piece of paper,
polyhedron, or protein) can be reconfigured or folded according to a few
constraints, which depend on the object being folded and the problem of
interest. In particular, we are interested in efficient algorithms for
characterizing foldability, and finding efficient folding processes, or in
proving that such algorithms are impossible.
There is a wide range of folding and unfolding problems, some going back
several centuries and still unsolved, like unfolding convex polyhedra, while
others are more recent like protein folding. In the last few years, there has
been tremendous progress on many of the fundamental problems in folding and
unfolding, yet some of the most important questions still remain open.
This leaves the area in an exciting state.
Many results in folding and unfolding can be characterized in the following
way. My favorite type of results are universality results which prove
that, in a certain model of folding, everything is possible. These results are
usually the most surprising. Typically they come with an efficient algorithm
for finding the folding; pure existential proofs are rare. If we cannot hope
to fold everything, the next best thing is to have an efficient (polynomial)
algorithm, both for detecting whether an object is foldable, and if so, for
finding an efficient folding. Sometimes even this is impossible: a hardness
result proves that even deciding whether an object is foldable in a
particular way is computationally intractable.
Linkage Folding: Carpenter's Rule Problem
The folding of linkages has been considered extensively in the context of
mechanics and robotics. Several interesting mathematical and computational
questions have come out of this area. In general, a linkage is defined by a
collection of rigid bars, connected at their endpoints called
vertices, to form a graph structure. A folding of a linkage
must preserve the connectivity between the bars, and must preserve the lengths
of every bar. Linkage-folding problems can be generally decomposed into
two types: when the bars are permitted to cross each other, and when the bars
cannot cross each other. I am most interested in the latter model, where
the problems become significantly more difficult.
Paper Folding: Origami Mathematics and Computational Origami
Origami (paper folding) has lead to an intriguing collection of problems to
study mathematically and computationally. Origami mathematics is a
recent branch of mathematics (whose major study started circa 1980) that
studies the properties of origami, such as what patterns you might get when you
unfold a flat origami. Computational origami is an even more recent
branch of computer science that explores algorithms for creating origami or
solving paper-folding problems. This field began in North America with Robert
Lang's work on TreeMaker (circa 1993).
The basic constraints in folding a piece of paper are that the paper
is folded continuously (no ripping), while preserving distances along
its surface (no stretching), and not causing the paper to self-intersect
(no crossing).
Polyhedron Folding and Unfolding
There are many different folding and unfolding problems involving polyhedra,
each with a different set of folding rules. For example, what surfaces of
polyhedra can be cut along some edges and unfolded into one flat piece without
overlap? The standard example is the well-known cross unfolding of the cube.
On the reverse side, what polygons can be glued at their edges and folded into
the surface of a polyhedron? A different problem, closely resembling paper
folding, is to treat the surface of a polyhedron as a paper model, and disallow
cuts: can every polyhedron be collapsed flat without tearing or stretching?
Applications
Most folding and unfolding problems are attractive from a pure mathematical
standpoint, from the beauty of the problems themselves.
Nonetheless, most of the problems have close connections to important
industrial applications. Linkage folding has applications in robotics,
hydraulic tube bending, and has connections to protein folding.
Paper folding has applications in sheet-metal bending, packaging,
and air-bag folding. Unfolding polyhedra has applications in
manufacturing, particularly sheet-metal bending.
These pages are organized according to the following topics. Currently I've
only listed problems on which I've written papers; surveys on other topics are
to come later.
- Fold and cut:
Fold a piece of paper flat and make one complete straight cut.
Now unfold the pieces and see what you get.
We prove that any pattern of cuts can be made in this way.
-
Folding silhouettes and wrapping polyhedra:
We show that "origami design is always possible," in the sense that
if you desire a given polyhedron (or a flat silhouette) you can fold it
out of a sufficiently large piece of paper. Furthermore, if you start
with a piece of paper that is white on one side and black on the other,
you can specify any desired black-and-white pattern on the polyhedron.
Open questions include how efficiently a square can wrap a polyhedron.
-
Map folding:
When can you fold a map? This questions turns out to have an efficient
algorithm (roughly linear-time) when the map is rectangular and has
horizontal and vertical creases. But if you add diagonal creases or
allow a more generally shaped map, deciding foldability is
computationally intractable (NP-complete)!
-
Unfolding polyhedra:
What polyhedra can be cut along edges (say) and
unfolded into a simple polygon in the plane? It is a long-standing open
question whether all convex polyhedra have this property, although there
are nonconvex polyhedra with triangular faces that do not.
- Folding
polygons into polytopes:
When can a polygon be folded and its
boundary glued together to form a convex polyhedron? This decision
question can be answered in polynomial time using a theorem of
the famous Russian geometer Aleksandrov.
- Linkages:
Into what configurations can you fold a piece of one-dimensional
``paper''
with given creases? Can we always get from one folding to another?
A recent result shows that every ``chain'' can do this in the plane,
but not every ``tree'' can. Furthermore, it is known that not all
chains in three dimensions have this property. For certain classes of
chains in three dimensions, though, the answer is yes.
-
Protein folding:
This is a major problem of interest in biology and physics.
We have started looking at a variation on the standard problem:
designing synthetic proteins that fold stably into a particular
configuration. So far we have shown the existence of such stable
foldings, i.e., proteins with unique minimum-energy states,
in a mathematical model of protein folding called the H-P model.
-
Hinged dissections:
Polygons can be hinged together at vertices to permit folding into a
variety of different shapes. Most of our results involve ``polyforms,''
that is, edge-to-edge gluings of several copies of a common polygon.
-
Hyperbolic paraboloids:
There is an easy way to fold an approximation to a (partial)
hyperbolic paraboloid out of paper. We've explored making sculptures
based on these units combined with polyhedra.
-
Disk hiding:
What is the largest disk you can cover on both sides (``hide'')
with a given sheet of paper and a limited type of folds?
Most of our results are about hiding a disk with one simple fold,
or with multiple simple folds in a square piece of paper.
I am currently also working on a project called ``flattening polyhedra'' (with
Martin Demaine, Barry Hayes, Anna Lubiw, and Joseph O'Rourke). Details to come
as soon as we have written the paper.
Here are a few good references on the web about folding and unfolding:
I am indebted to Tom Hull and Rob Lang for introducing me to origami
mathematics and filling me in on much of the background material.
