6.849: Geometric Folding Algorithms: Linkages, Origami, Polyhedra (Fall 2020)

In the first class (C01), we'll do the following:

• I'll give a very brief technical overview of the content of the class — why we care about folding, and a sampling of the cool mathematical results we'll be covering. (If you want more, watch the "Extra Video" link for C01 on the lectures website.)
• I'll describe the requirements for the class (for those taking the class for credit).
• I'll very briefly describe the software tools we'll be using to meet. You can read the documentation for Coauthor, Cocreate, and Comingle.

• Then we'll solve problems together! This will be the bulk of the time we spend in most classes, including this one. We've prepared a bunch of cool problems that you can sink your teeth into without having any background yet. The problems range from solved problems (puzzles we know the answer to) to open problems (unsolved research questions, many of which we should be able to make progress on) to design problems (make something new!) to coding problems (for the programmers). You can choose your own adventure and work on any subset of the problems you like in whatever groups you like. You can jump from problem to problem (room to room) over the course of the class. You can also work on the problems between classes, and post your progress/ideas to Coauthor.

On the design side, we'll see how simple folds are enough to fold any 2D shape, and with slightly more general folds, we can fold any 3D shape even with a two-color pattern on the surface.

On the foldability side, we'll see how to efficiently determine whether a crease pattern with mountains and valleys indicated can be folded flat in two interesting cases: 1D pieces of paper (in other words, parallel creases in a strip of paper) and 2D rectangular maps.

We also get started on the tree method of origami design, developed by many Japanese origami designers over the years, and turned into an algorithm and computer program TreeMaker by Robert Lang. This method has been the most successful in transforming complex origami design, and we'll cover more of it next lecture.

First up is the tree method, whose software implementation TreeMaker I demoed at the end of Lecture 2. I'll describe how it lets us fold an optimum stick-figure (tree) origami base, although computing that optimum is actually NP-complete (as we'll see in Lecture 6). This algorithm is used throughout modern complex origami design; I'll show some examples by Robert Lang and our own Jason Ku.

Second we'll look at a simple, fully understood case: the smallest square to fold a cube.

Third we'll look at a classic problem that we made progress on recently: folding an n × n checkerboard from the smallest bicolor square.

Finally we'll look at the latest and most general method, Origamizer, for folding any polyhedron reasonably efficiently. Here we don't have a nice theoretical guarantee on optimality, but the method works well in practice, provably always works, and has other nice features such as watertightness.

His lecture will be about his perspectives on artistic origami design. Lecture 3 outlined the tree method algorithm of origami design. Now we'll see how this method applies in real-world examples.

The first half of the lecture will introduce the artistic side of representational origami. In origami, as in many disciplines, familiarity with the canon of work that already exists can be quite useful in understanding avenues for future creative development. Thus we'll cover the works and styles of a sampling of the world's most renowned paper folders.

The second half of the lecture will focus on the actual design of representational origami art. We will briefly review tree theory, weigh the pros and cons of this design method, and emphasize the relationships between a tree, a circle/river packing, and the locus of possible hinge crease in a uniaxial base. Finally, we'll go through the process of designing an origami model with, then without, the help of TreeMaker.

This lecture will present my recent studies on computational origami algorithms and interactive systems to enable architectural designs. The topics include the algorithm for origamizing arbitrary polyhedral surfaces, freeform variation method of different types of origami patterns, and rigid origami theory, design, and physical implementation. The proposed systems are freely available from my website (http://www.tsg.ne.jp/TT/software/): Rigid Origami Simulator, Origamizer, and Freeform Origami. These systems enable origami designs for architecture, i.e., architectural origami, as well as an origami bunny.

First, continuing our theme from Lecture 3 on efficient origami design, we'll see how subsets of a single hinge pattern are enough to fold any orthogonal shape made up of cubes, whereas other approaches use a completely different set of creases for each origami model you want. In general, we can fold n cubes from an O(n) × O(n) square of paper. In the special case of “orthogonal mazes”, we can waste almost no paper, with the folding only a small constant factor smaller than the original piece of paper. You can try out this yourself.

Second, we'll see a few ways in which origami is hard. Specifically, I'll give a brief, practical introduction to NP-hardness, and prove three origami problems NP-hard:

• folding a given crease pattern via a sequence of simple folds;
• flat folding a given crease pattern (using any folded state);
• optimal design of a uniaxial base, even when the tree is just a star.

Afterward, we'll briefly look at a couple of related topics: how to maximally inflate a teabag or other polyhedral surface by folding, and what kind of foldings are possible with curved creases. On the latter topic, I'll overview a big ongoing project in which we're trying to reconstruct the mathematics underlying a beautiful series of sculptures folded by David Huffman from the 1970s–1990s.

Then we'll focus on Kempe's Universality Theorem: there's a linkage to sign your name, or more mathematically, trace any polynomial curve. This proof introduces a bunch of cool gadgets, in particular to add angles and multiply (or divide) angles by constant factors.

We'll cover two main theorems characterizing “generically” rigid graphs in 2D. Henneberg's Theorem, from 1911, gives a nice and direct characterization, but it's hard to turn into an algorithm. Laman's Theorem, from 1970, is intuitively harder to work with, but turns into a fast (quadratic-time) algorithm.

Unfortunately, this is all just for 2D, and we don't know any good characterizations for generic rigidity in 3D. I'll briefly describe some nice theorems about the rigidity of convex polyhedra in 3D, though, which in particular explain why Buckminster Fuller's geodesic domes stand up.

Although not obviously related, the rigidity tools we build up allow us to prove the existence of actual folding motions between any two configurations of “chain linkages” (whose graphs are paths or cycles) whose edges aren't allowed to cross. This Carpenter's Rule Theorem (which was essentially my PhD thesis) kicks off our coverage of understanding when linkages can “lock”.

1. Does every convex polyhedron have an edge unfolding? This is also the oldest problem, implicit back to 1525.
2. Does every polyhedron (without boundary) have a general unfolding? This is one of my favorite open problems.

On the unfolding side, we'll cover “vertex unfolding”, which is a variation on edge unfolding kind of like hinged dissections. We'll prove that this type of unfolding exists, even for nonconvex polyhedra, provided every face is a triangle. Then we'll cover recent breakthroughs in general unfolding, for orthogonal polyhedra.

On the folding side, we'll prove Cauchy's Rigidity Theorem: convex polyhedra have exactly one convex realization (viewing faces as rigid and edges as hinges). Then we'll show how to extend this to Alexandrov's Uniqueness Theorem: if you glue up the boundary of a polygon, there's at most one convex polyhedron you can make. (Next lecture we'll see how to actually get one.)

The main tool in this area is called Alexandrov's Theorem, from 1941, which characterizes when a gluing of the boundary of a polygon will result in a convex polyhedron; plus, as we saw last lecture, that convex result is always unique. We'll sketch a proof of this theorem as well as recent algorithms for finding the convex polyhedron.

With this tool in hand, we'll explore some different properties of gluings. Some polygons, in fact "most" in a certain sense, have no Alexandrov gluings. Convex polygons, on the other hand, always do. Some polygons have infinitely many gluings, but this always happens in a controlled way with a few "rolling belts". Along the way we'll see gluing trees, a useful tool for analyzing gluings that we'll use in the next lecture for algorithms to find gluings.

• common unfolding of a regular tetrahedron and near-cube
• common unfoldings of Platonic solids and near-regular tetrahedra
• common unfoldings of boxes of different sizes
• common unfoldings of many polycubes
• orthogonal unfoldings with nonorthgonal foldings
• smooth Alexandrov's theorem, applied to smooth convex shapes (D-forms)
• unfolding smooth convex polyhedra (prismatoids)
• wrapping (paper folding) smooth surfaces like spheres, using a new definition of origami, where distances can shrink instead of necessarily staying the same

• Span: What's the farthest or nearest you can fold the endpoints of a fixed-angle chain?
• Flattening: When does a fixed-angle chain have a non-self-intersecting flat state?
• Flat-state connectivity: When can a fixed-angle chain be folded without self-intersection between every pair of flat states?
• Locked: When is a fixed-angle linkage locked? In particular, we'll show that all states of a fixed-angle chain producible by a simple model of the ribosome (which includes all flat states) can reach each other.

Then we'll turn to a fun problem of interlocked linkages. It's known that you need five bars to lock an open chain, but can you interlock multiple chains each with less than five bars? The answer is yes, with a nearly complete characterization of the possibilities. One consequence we'll see is how to cut a chain of n bars into around n/2 pieces that are not interlocked, while n/4 pieces are necessary.