00:00:13.790
Thank you for having me. As Joan said, my name is Amy Wibowo, and I am known as Sailor Hg on the Internet. I recently made the switch from being a full-time developer to focusing on computer science education. I care a lot about the ways computer science is related to other subjects, specifically the intersection of technology and art. That's why today, I'm going to talk to you about the mathematics of origami, particularly the mathematics behind one of my favorite origami theorems.
00:00:24.990
So, a little bit of background: when I was in college studying computer science, I had to take a class that fulfilled an advanced algorithms requirement. Instead of taking a class called Advanced Algorithms, I opted to take a class called Paper Folding Algorithms, which fulfilled the same requirement. That meant we spent every day in the classroom proving and discussing different theorems about origami, and this one was my favorite.
00:00:46.020
It's called the Fold-and-Cut Theorem, and it states that you can generate any polygonal shape from a single piece of paper with just one cut. Any polygonal shape and just one cut! That's a really big claim, but it was proved by the professor who taught the class, along with Martin Demaine of MIT and Professor Anna Lubiw at the University of Waterloo. Now, I'm going to demonstrate this on a piece of paper.
00:02:03.670
So, I'll show you the unfolded piece. The unfolded piece of paper is a swan, and if you fold it along these lines, you'll be able to cut out the swan with just a single cut. This is actually a pretty old puzzle. The first reference to it is in a Japanese puzzle book from 1721, which challenges the reader to cut out a shima, a lightning-shaped figure said to guard against evil spirits, from a single piece of paper with just one cut.
00:02:29.230
To reiterate this theorem again in cartoon form: you can generate any polygonal shape from a piece of paper with a single cut. You might just need to fold the paper many times before making the cut. So, my question becomes: assuming that this is true, how and where do we fold the paper before we make that single cut to make this possible?
00:03:44.690
There are a couple of ways of thinking about this conceptually. We can envision it as wanting to fold a piece of paper so that everything that's part of this cat is above a line and everything that's not part of the cat is below the line, and then we cut at that line. Another way to think about it is to fold the paper so that the outline of the cat, which is exactly what we want to cut, is all aligned on the same line. This perspective will be helpful for coming up with an algorithm that tells us the necessary folds before the cut.
00:04:34.490
Let’s consider simple examples of how we can get lines to align on a piece of paper. For instance, if you want the top and the side of a piece of paper to be aligned, you would fold at the 45-degree angle between them. Then you have the top and the side aligned. If you have two lines randomly drawn on a piece of paper and want to align them, you'd fold somewhere in between them. If you extend those lines until they meet somewhere off the paper, you will find that we are folding along the angle bisector of those two lines. Folding along that angle bisector is how we align angles and lines.
00:05:59.040
Now, how do we generalize this for getting all the edges of a polygon to line up? For example, what happens if we have a complicated polygon, and some of the angle bisectors intersect with one another? We would calculate what mathematicians call a straight skeleton. It’s called a straight skeleton because when you calculate it, it ends up looking like it could be the actual skeletal support structure for that object. To calculate it, you shrink the original shape while maintaining a constant perpendicular distance from the original edges. The path of the vertices as the shape shrinks is the straight skeleton.
00:07:15.090
So far, this path is consistent with our idea that the angle bisectors of a shape are an important component of calculating how to align the sides. As you're shrinking the shape, you might encounter three types of edge cases. First, the shape might become so small that it becomes a point. If this happens, you stop because once the shape is a point, it can't shrink anymore. The simple skeleton is the path from the original vertices to that single point, as indicated in this figure.
00:08:18.440
Another edge case is when two edges might merge into a single edge, just like the top and bottom of this rectangle do. What does this mean for calculating the straight skeleton? You include that merged edge in the straight skeleton along with the path of the vertices to that merged edge, as shown in the bold lines here. Lastly, as you shrink a shape, you might find that it separates into two distinct shapes, and that’s totally fine. You just apply the algorithm to both shapes recursively.
00:09:17.600
After reading a lot of research papers, I found that most robust implementations of a straight skeleton solver were the subject of PhD theses. The kinds of things that people documented as difficult were input polygons with extreme concave sections, polygons with a spiral shape, and dealing with floating point numbers. While I didn’t have time to write a PhD thesis for this talk, I did write a solver that can handle simpler input polygons using Ruby. I used the Shoes graphical toolkit and the Ruby geometry gem, which contains a lot of helpful geometry functions. Now, I’ll demo the Shoes app.
00:08:56.300
I can't see, but I think this is the shape. Okay, so we draw the Ruby, and when we push this button, it's going to shrink the Ruby until it becomes a point and then draw the straight skeleton.
00:09:39.430
Now that we have a skeleton, can we fold along it to cut out the Ruby with a single cut? Almost. It turns out the straight skeleton provides most, but not the full set of folds that we need to create a shape with a single cut. Why do we need more folds? To answer this question, we need to delve a little deeper into computational folding theory.
00:11:19.900
Here is a simple example of why the straight skeleton isn't fully sufficient for our purposes. This is the straight skeleton for a rectangle. What happens when we try to fold along skeleton lines? If we try to fold along those lines, we see that they just don't fold into a flat shape. We need the piece of paper to be flat before we can make our single cut.
00:12:07.610
Not all sets of edges fold flat, and foldability is a whole other area in the field of computational origami. It formalizes which sets of edges will fold flat, which won't, and which might be impossible to fold. A set of edges that can be folded flat is called flat-foldable. For this particular shape, we could fold it flat if we added perpendicular helper lines that extend from the inner skeleton to the edges of the rectangle.
00:12:41.310
Now, let's demonstrate how adding these two additional lines allows us to flat fold the rectangle. Now that we have these two lines, we can indeed fold it flat.
00:13:07.860
So how do we generalize this? How do we add a few folds for the general case to make any straight skeleton flat-foldable? We can establish that any helper folds must meet the shape edge at 90 degrees, ensuring they won't interfere with the existing alignment of the edges. We draw perpendiculars from every vertex of the straight skeleton to the edges of the shape. It turns out we won’t need all of them, but having none of them won’t hurt foldability or affect one-cut ability.
00:14:24.450
Here’s what we get if we draw a perpendicular from every straight skeleton vertex in the diagram we generated earlier. Now, I’ll show you a live demo of cutting the Ruby.
00:15:15.000
Here is the Ruby. We fold it on the straight skeleton lines and some of the perpendicular helper lines.
00:15:31.800
This project is super exciting to me, as there are still many ways to take it further. For example, I would love to add these perpendiculars to the Ruby Shoes app, and on top of that, to assign mountain and valley foldability. Yet another part of foldability theory is that you can systematically determine whether folds go in valley folds or whether they go outward as mountain folds.
00:16:10.940
Additionally, I want to read more theses so I can implement a program that handles more edge case traits. Thank you so much for listening! Come find me during the break if you'd like to talk about origami, the intersection of coding and art, computer science education, or if you just want some stickers.
00:17:20.490
The question is whether the Shoes app is online. I want to clean it up a bit more before I put it online, but it is definitely possible to use. People who are serious about origami tend to use thinner paper so that their models are physically possible.
00:17:30.920
The question was whether paper thickness poses limits on folding. Yes, it is possible to generate a folding that will eventually be physically impossible due to thickness. Thus, serious origami artists often use thinner papers.
00:17:54.050
Finally, the question was whether these algorithms are applicable to other fields. Some examples the professor gave included applications in satellites and space exploration robots, where this principle can enable solar panels to fold up very compactly.
00:18:38.780
I thank you all for your attention!
