DIMACS
The Center for Discrete Mathematics
and Theoretical Computer Science

Reconnect Satellite Conference 2004:
St. Mary's College

Reconnecting Teaching Faculty to the Mathematical Sciences Enterprise

July 11 - July 17, 2004
(Sunday evening through Saturday afternoon)


Folding and Unfolding in Computational Geometry
S Joseph O'Rourke, Smith College, orourke@cs.smith.edu
http://cs.smith.edu/~orourke/

The folding of flat material (e.g., paper or metal), and the unfolding of a surface in 3D to a planar state, are complementary processes of increasing importance at the nexus between pure mathematics and a variety of application areas. Folding one-dimensional (1D) "linkages" is a model for protein folding. Designing origami foldings of (2D) flat paper from the desired final folded shape is an ancient problem with recent advances. Unfolding a (3D) polyhedron to a nonoverlapping piece is a first step in manufacturing objects by bending aluminum.

This course will cover the mathematical and algorithmic issues of folding and unfolding, touching upon the application areas as appropriate. I'll be following the outline of a book nearing completion, coauthored with Erik Demaine at MIT. Five novel features of this material are:

We will start with 1D linkages, paying particular attention to "locked linkages," which have a relation to protein folding. Next we will study 2D, in particular, computational origami, including the difficulty of folding a map and flattening a box. Lastly we will explore unfolding 3D polyhedra to flat "nets," and the reverse process of folding polygons to polyhedra, an area with application to manufacturing. In all three areas the most prominent unsolved problems will be highlighted.

There is room in these topics for both pure mathematical research, and pure computer science theory research, but the richest aspects lie at the junction between the two: Progress on the mathematical questions seems to demand computation, and algorithmic progress is impossible without geometric understanding. Participants who bring expertise in either area will benefit from the cross exposure.

Prerequisites: Most of the material is accessible to any Mathematics or Computer Science professor. Familiarity with Discrete Mathematics, in particular, the basics of graph theory, will help. Some material can only be fully appreciated by those who understand the concepts of Algorithms. The theory of NP-completeness is used, but not extensively; knowledge of that is not essential. Knowledge of the basics of Differential Geometry will enhance the experience, but again is not essential.


Back to Main Page