6.849: Geometric Folding Algorithms: Linkages, Origami, Polyhedra (Spring 2017)

In our first class, I'll give a whirlwind tour of the entire class in about an hour, talk about the format of the class, and then we'll solve some problems! In general, the format of the class will focus on problem solving — both on solving solved problems (like you would on a pset) but collaboratively in class, and on solving unsolved problems that no one knows the answer to. In addition to mathematical problems, we'll have design and programming problems/challenges.

To facilitate problem solving, we'll be using (open-source) software I wrote called Coauthor. To that end:

1. Please sign up for an account now here: https://coauthor.csail.mit.edu/6.849-2017/
2. Please fill out this survey so that we can give you permission to use Coauthor, and get a sense of who is taking the class: https://goo.gl/forms/QzEyhK2lhcHcUZy33
3. Please bring a laptop (or tablet) to class.

In this first class, we'll work on problems related to strip folding.

I'll give an introduction to NP-hardness — roughly what it means (likely no efficient algorithm to solve a problem) and how to prove problems NP-hard (by reductions). In particular, I'll show NP-hardness proofs for

• Ruler Folding (fold a 1D hinge pattern down to a given length), and
• Simple Folding (fold a given crease pattern by a sequence of simple folds).

We'll also distinguish between weak and strong NP-hardness, which depends on how large the numbers in the problem are allowed to get.

Then we'll work on problems related to simple folds.

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.

I'll show (at a pretty high level) two more proofs of NP-hardness:

1. flat foldability of deciding whether a given crease pattern, or a given mountain-valley pattern
2. disk packing, which corresponds to the tree method for star trees

I'll also mention some new results in cube/sphere wrapping.

Then we'll work on problems related to seam placement.

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.

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.

We'll have our first (of several) guest lectures: Chuck Hoberman. Currently teaching at Harvard GSD, Chuck is a brilliant mechanism designer, famous for the expanding Hoberman sphere and many architectural installations. See some of his work.

Then we'll work on problems related to fold & cut and extrusion folding.

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.

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.

We'll have Duks Koschitz (from Pratt) giving a guest lecture about David Huffman's curved crease origami, which was the subject of his PhD thesis at MIT in Dept. of Architecture. Huffman was a pioneer of curved-crease folding, with beautiful work; he was also an MIT student and professor. His work was recently acquired by MIT Museum and is being cataloged.

Then we'll work on problems related to fold & cut.

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.

Prof. Tom Hull is visiting from Western New England University, speaking about the mathematics of self-folding and rigid origami. Tom is one of the original origami mathematicians — he and I were PhD students at the same time (though in different countries), and he introduced me to all the people and papers in the field.

Then we'll work on problems related to rigidity.

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”.

This class we have Prof. Samuel Felton from Northeastern University guest lecturing about folding robots. Sam is an expert in folding robots; in particular, he was the lead author on the self-folding robot from Science (which was his PhD work at Harvard). It should be fun!

Then we'll work on problems related to locked linkages.

We will have a guest lecture by Benjamin Parker, one of my favorite artists in the world of origami tessellations. You can see some of his work on his website, http://www.brdparker.com/.

Then we'll work on problems related to polyhedron unfolding.

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.)

YQ Lu will give a guest lecture about his work in paper sliceforms, as embodied by his software Sliceform Studio [https://www.sliceformstudio.com/]. See his resulting artwork at https://www.sliceformstudio.com/gallery.html.

Then we'll work on problems related to gluings and sphere wrapping.

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.

Jason Ku will give a lecture on how to fabricate folded structures using thick materials, and how to design crease patterns that satisfy boundary conditions. You can find both his academic and artistic folding work at http://jasonku.mit.edu/.

Then we'll work problems about boundary conditions, common unfolding, and protein folding.

• 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.

This class is the last one in which we solve problems. Specifically, we have a couple of problems related to protein folding in the HP model, and a few about interlocked linkages. In addition, I'll summarize the past and future of the class:

PAST: I'll review what we accomplished in all of our problem solving during the semester.

FUTURE: I'll present the 1-slide summaries of the presentations to come in the final two class sessions (C12 and C13).

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.