The answer turns out to be any pattern of straight cuts. Try it out yourself by printing one of our several examples.
Another early reference to folding and cutting is a July 1873 article “National Standards and Emblems” in Harper's New Monthly Magazine, volume 47, number 278. This article tells the story about Betsy Ross and her relation to the American flag. It claims that in 1777, George Washington and a committee of the Congress showed Betsy Ross plans for a flag with thirteen six-pointed stars, and asked whether she could make such a flag. She said that she would be willing to try, but suggested that the stars should have five points. To support her argument, she showed how easily such a star could be made, by folding a sheet of paper and making one cut with scissors. The committee decided to accept her changes, and George Washington made a new drawing, which Betsy Ross followed to make the first American flag. One method for folding and cutting a five-pointed star is described on ushistory.org's Betsy Ross page. Sadly, this story is probably false, but it's still makes for an early reference.
Before Houdini was a famous escape artist, he was a general magician. His 1922 book Paper Magic (E. P. Dutton & Company, pages 176–177) describes a method for making a five-pointed star. According to David Lister, this book appears to have been ghostwritten by another magician, Walter Gibson, but Houdini still may have performed the trick.
Another magician, Gerald Loe, studied the fold-and-cut idea in some detail. His 1955 book Paper Capers (Magic, Inc., Chicago) describes how to cut out arrangements of various geometric objects, such as a circular chain of stars.
Martin Gardner wrote about the fold-and-cut problem in his famous series in Scientific American (“Paper cutting”, chapter 5 of New Mathematical Diversions (Revised Edition), Mathematical Association of America, Washington, D.C., 1995.). Gardner was particularly impressed with Loe's ability to cut out any desired letter of the alphabet. He was also the first to state cutting out complex polygons as an open problem. What are the limits of this fold-and-cut process? What polygonal shapes can be cut out?
There are two methods for solving this problem, by different sets of people. I call them the straight-skeleton and disk-packing methods. You can read descriptions of them below, or watch the free online video lecture describing them:
Analyzing the straight-skeleton method, from the book.
The straight skeleton consists of the majority of the creases and achieve the desired “lining up” of cuts. In addition, there are perpendicular creases. Basically, from each vertex of the straight skeleton, we shoot a ray perpendicular to each reachable cut edge, and the ray “bounces” (reflects) through any skeleton edges it meets.
The difficult part is proving that the straight-skeleton creases together with a subset of the perpendicular creases (and a few more auxiliary creases) can be folded into a flat origami. This is done by exhibiting a folded state, that is, by demonstrating how the piece of paper looks when folded. This folded state must satisfy the properties that each face is isometrically preserved and that paper does not intersect itself.
The most detailed description is the book Geometric Folding Algorithms: Linkages, Origami, Polyhedra. The full paper (which includes all proof details) is still in progress. The longest description includes many of the proofs and was published in the Proceedings of the Japan Conference on Discrete and Computational Geometry (JCDCG'98), to appear as a volume in Lecture Notes in Computer Science. A 2-page description of the method (without proofs) appears in the Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99).
This work is related to Robert Lang's TreeMaker, although it was initially developed in isolation. The intersection is that they both solve the fold-and-cut problem when the faces (shapes to be cut out) are all convex. Both TreeMaker and our work extend far beyond this common base, in different directions. Essentially, TreeMaker tries to collapse a polygon to a specified folded shape but only addresses convex polygons, whereas the straight-skeleton method focuses on the unfolded shape and addresses nonconvex and disconnected polygons.
An example of the disk-packing method, from the paper.
The most detailed description is the book Geometric Folding Algorithms: Linkages, Origami, Polyhedra. The paper “A Disk-Packing Algorithm for an Origami Magic Trick” also describes the method in detail, though it has some small issues. The most recent version includes some simplifications, and appears in the Proceedings of the 3rd International Meeting of Origami Science, Math, and Education (OSME 2001). The original version was published in the Proceedings of the International Conference on Fun with Algorithms (FUN'98).
Our use of disk packing is quite different from Robert Lang's TreeMaker, although it is intriguing that the same method comes up in two different contexts in origami mathematics.
A new paper with Martin Demaine, Andrea Hawksley, Hiro Ito, Po-Ru Loh, Shelly Manber, and Omari Stephens considers what happens when we restrict the folds to a sequence of simple folds, folding along a single line at a time.
Ivars Peterson briefly describes the fold-and-cut results in his article, “Fold-and-Cut Magic”, which appears in Science News, volume 162, number 22, November 30, 2002.
Joseph O'Rourke briefly describes the two fold-and-cut methods in his “Computational Geometry Column 36”, which appears in International Journal of Computational Geometry and Applications, volume 9, number 6, pages 615-618, 1999; and SIGACT News, volume 30, number 3, issue 112, September 1999, pages 35-38.
One application of the fold-and-cut theorem is the design of the logo for CCCG 2001.
Some of our earlier papers on the fold-and-cut problem are the following: