The Origami Polygon Cutting Theorem
By Eric Biunno
Proof of Algorithm
Links & References
5]. When discussing origami, we usually picture elaborate and beutiful paper animals. But we also realize that this art is closely related to mathematics or geometry. This scientific aspect, however, was not extensively studied until about 1980, when Origami mathematics emerged as a field .
There are a multitude of ways to fold paper and different techniques can be used to achieve certain sculptures. In the study of origami mathematics, one would like to relate these notions of 'paper' and 'folds' to mathematical concepts. We can then use existing geometrical theorems to discover new theorems that relate to origami. The theory and algorithm presented in "Folding and Cutting Paper" by Erik D. Demaine, Martin L. Demaine and Anna Lubiw in 1998  will be discussed here.
Well, the origami polygon cutting theorem is as follows:
Let me introduce some preliminary terminology so that we can better understand this theorem.
A plane graph is a planar graph where every edge is straight and has positive length, and every pair of edges intersects only at a shared vertex. Infinite lines, half-infinite lines, and line segments are represented by edges with zero, one, or two actual vertices respectively.
A crease pattern is simply a plane graph (figure 1). This is the collection of lines and segments which will show us where to fold our piece of paper in order to get the shape we want.
We must also know how to fold our paper, or more precisely, which direction we should fold the paper at every edge of our crease pattern. We say an edge of the crease pattern is a mountain edge if it must fold an angle Pi relative to the top side of the paper (fold away from you) and it is a valley edge if it must fold an angle -Pi relative to the top side of the paper (fold towards you).
Figure 1: A Crease Pattern For A Simple Polygon. Mountain edges are dash-dotted, valley edges are dashed
An origami or folding of a crease pattern is a continuous function from R2 to R3 with the following properties:
Note that a folding presents us with the final folded state, not the process of how to get to the folded state.
A flat origami is a folding whose image lies on a single plane. The final state of the folded paper is flatened.
A cut is just a line. We want to remove this line from our plane graph somehow. There are two ways of doing this, each defines a type of cut:
Figure 2: Mathematical cuts can cut along the fold line, scissor cuts cannot.
So, we can now see what we want to achieve:
Given a plane graph --which we call the cut graph-- drawn on a piece of paper construct a crease pattern that once folded aligns all the edges on to a single line and nothing else is on that line. This line will be our cut line, and after performing the cut and unfolding our pieces, we will have seperated the regions defined in our cut graph.
1]. Solving the fold-and-cut problem can be split up into two steps:
Finding a crease patternStraight Skeleton
A natural way to get all the edges of a polygon to line up onto a single line is to fold along the bisector of their extensions. A generalization of this idea to arbitrary cut graphs is the straight skeleton (figure 3). The straight skeleton structure is defined to be the trajectories of the vertices as we shrink the faces of the cut graph. Shrinking consists of continuously insetting each vertex towards the interior of the face, so that at any particular time:
Figure 3: Finding the Straight Skeleton of a Polygon.
There are a few algorithms for finding the straight skeleton of a given plane graph: Felkel & Obdrzálek , Aichholzer & Aurenhammer . A very good explanation of the straight skeleton along with an interactive applet can be found at David Bélanger's Designing Roofs of Buildings. We are not too concerned with the straight skeleton algorithm although the running time and the resulting crease pattern are dependent on it. The fatsest algorithm to date runs in O(n17/(11+E)). We are instead more interested with the properties of the straight skeleton itself.
Properties of the Straight Skeleton
Let us first note that the straight skeleton is a plane graph. Here are some other properties:
The main idea here is to add a fold perpendicular to an edge of the given cut graph. This would maintain the property that the edges of the cut graph line up. Let us define what a perpendicular is and how to obtain them. The perpendicular associated with any point p in the plane consists of a collection of line segments, rays, and lines called perpendicular edges, each associated with a straight skeleton face.
A recursive definition of perpendicular edges is as follows:
We can seperate perpendiculars into two categories, real perpendiculars and imaginary perpendiculars. A real perpendicular is a perpendicular that is incident to a vertex of the straight skeleton of the cut graph. Imaginary perpendiculars are simply all other perpendiculars. Together, all of the real perpendicular edges form the perpendicular graph (see figure 4).
Figure 4: Finding the Perpendicular Graph of a Polygon.
There are two noteworthy properties of perpendiculars:
Mountain-Valley AssignmentThe next step of the algorithm involves labeling the edges of the crease pattern as mountain or valley edges. The assignment is performed according to whether the faces of the cut graph lie on one side of the cut line or the other. For faces of the given plane graph that are above the cut line:
Now we can fold our original cut graph and cut along the cut line (the edges of the cut graph), to get the desired result. This is the algorithmic aproach used in  to solve the fold-and-cut problem for a given cut graph.
Figure 5: Assigning Mointain (dashed) or Valley (dotted) Folds To Edges.
In order to prove the above algorithm let us examine two other structures related to perpendiculars, corridors. Corridors are simply the faces of the perpendicular graph. Unlike in usual plane graphs, a corridor never consists of a bounded simply connected region. We can classify corridors in two ways: by topology and by wall count.
Two classifications of corridors:
Figure 6: The Four Types of Corridors
The other structure we wish to examine is called an accordion (figure 7). Consider a corridor, the creases intersecting it, and the mountain-valley assignment for those creases. An accordion is a folded state of this.
Figure 7: Accordion: Folding A Corridor
Let us prove the algorithm described above solves the fold-and-cut problem for crease patterns which have no circular corridors. To do this we must first prove that an accordion exists and lines up all edges of the cut graph contained in its corridor.
If creases completely cross the corridor, then a folded state exists:
Finally we have to show that this folding can be folded flat (folded down to a single plane). We can do this by modeling accordians by a tree:
Folding this collection of accordions flat onto one plane reduces to folding a tree (figure 8).
This tree corresponds to the xy projection of the folded model:
Figure 8: Folding of A Tree.
To start the applet make sure you have the latest Java Runtime Environment installed, and click the button below, it will open in a pop-up window. You can also save a screenshot and print out the shape on to paper, and try it out.
Any simple polygon can be drawn, but computation of the straight skeleton is only guaranteed for convex polygons in this implementation. It may compute the correct straight skeleton for non-convex polygons. The perpendiculars depend on the straight skeleton and are correct, assuming the straight skeleton is correct. Mountain-Valley assignments are also correct for convex polygons.
This applet is inspired by, and shares some code with David Bélanger's Applet .