and Theoretical Computer Science

St. Mary's College

July 11 - July 17, 2004

(Sunday evening through Saturday afternoon)

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:

- Most of the material is accessible with only high-school mathematics, much of the remainder is accessible to students who have been exposed to algorithm analysis, and only a fraction requires advanced mathematics or computer science training.
- The material has an immediate physical, nearly visceral appeal, as it involves thinking about material common everyday experience (i.e., paper folding, or crushing boxes) in novel ways. Thus students can use their intuitions as firm bases (supplemented by model building) from which to jump into new areas.
- The topic has real-world practical applications, as indicated above, so it touches reality directly.
- The frontier is proximate: Students can, in a just an hour or two, so thoroughly grasp the issues that they can actively work on unsolved problems.
- Although the open problems are accessible, they seem to be deep, so that their pursuit will naturally draw students deeper into mathematics and computer science.

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