Erik Demaine's Folding and Unfolding Page


Five Intersecting Tetrahedra origami model
designed by Tom Hull
folded by Vanessa Gould

Introduction

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.

Topics

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.
  1. 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.

  2. 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.

  3. 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)!

  4. 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.

  5. 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.

  6. 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.

  7. 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.

  8. 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.

  9. 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.

  10. 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.

References

Here are a few good references on the web about folding and unfolding:

Acknowledgments

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.

Last updated November 28, 2010 by Erik Demaine.