Cxx indicate class sessions / contact hours, where we solve problems related to the listed video lectures.
Lxx indicate video lectures from
Fall 2010 (with a different numbering).
The Lxx videos are required viewing before attending the Cxx class listed above them.
Extra Videos are optional extra videos from Fall 2012 (with a different numbering), if you want to know more
C01  Feb. 8 
[+]
Class format: Inverted lectures, problem solving, requirements. Content overview: Applications to robotics, graphics, mechanics, manufacturing, medical, aerospace, biology, sculpture, architecture. Linkages, paper, polyhedra. Foldability/analysis vs. design/synthesis. Universality, decision, and hardness results. Sample results. 
[Notes]  [Slides]  [Extra Video]  

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 (opensource) software I wrote called Coauthor. To that end:


C02  Feb. 15 
[+]
Review: Simple origami: Simple folds, strip folding, singlevertex crease patterns.
NPhardness: Reductions, weak vs. strong, ruler folding, simple folding. 
[Notes]  [Slides]  
I'll give an introduction to NPhardness — roughly what it means (likely no efficient algorithm to solve a problem) and how to prove problems NPhard (by reductions). In particular, I'll show NPhardness proofs for
We'll also distinguish between weak and strong NPhardness, which depends on how large the numbers in the problem are allowed to get. 

L01 
[+] Origami intro:
Piece of paper, crease pattern, mountainvalley assignment. Universality: Folding any shape (silhouette or gift wrapping). Simple folds: 1D flatfoldability characterization, 2D mapfolding algorithm.  [Notes]  [Slides] 
[Video] [Extra Video] 

This lecture kicks off a series of lectures about origami. It focuses on
a relatively simple kind of origami, called “simple folds”,
which involve folding along one straight line by ±180 degrees.
These are some of the most “practical” types of folds from
an automated manufacturing standpoint, are wellstudied mathematically,
and a good warmup before we get to complex origami folds which fold
many creases at once.
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 twocolor 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.  
L02 
[+]
Singlevertex crease patterns: Characterizations of flatfoldable
crease patterns and mountainvalley patterns, combinatorics of the
latter, local flat foldability is easy. Tree method of origami design: Introduction, uniaxial base, demo. 
[Notes]  [Slides]  [Video] [Extra Video] 

This lecture is about the local behavior of flat folding
around each vertex of a crease pattern. In other words, we study
each vertex individually, by characterizing all singlevertex
crease patterns and mountainvalley patterns that are flat foldable.
Then we look at how to combine multiple vertices into
a "locally foldable" crease pattern.
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.  
C03  Feb. 22 
[+]
NPhardness: Flat foldability, disk packing. Origami design: TreeMaker, Origamizer, cube/sphere wrapping. 
[Notes]  [Slides]  
I'll show (at a pretty high level) two more proofs of NPhardness:
I'll also mention some new results in cube/sphere wrapping. 

L03  [+] Efficient origami design: Tree method, TreeMaker, uniaxial base, active path, rabbitear molecule, universal molecule, Margulis Napkin Problem; cube folding, checkerboard folding; Origamizer, watertight, tuck proxy.  [Notes]  [Slides]  [Video] [Extra Video] 

This lecture is all about efficient origami design.
We saw in Lecture 1 how to fold anything impractically.
Now we'll see how to fold many shapes practically.
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 stickfigure (tree) origami base, although computing that optimum is actually NPcomplete (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.  
L04  [+]
Architectural Origami: Origamizer, Freeform Origami,
Rigid Origami Simulator, cylindrical origami, thick origami
(guest lecture by Tomohiro Tachi) 
[Slides]  [Video] [Extra Video] 

Origami, the art of folding a sheet of paper into various forms without
stretching or cutting, can be applied to structural engineering and design
purposes. The applications include the forming of a 3D surface without
assembling multiple parts and the construction of kinetic structures such as
retractable roofs, openings, temporary shelters, and space structures.
In the design process of such applied origami, it is very difficult for
the designer to control the form to fit design contexts while preserving the
necessary functionalities of the original patterns. Therefore, without
sufficient knowledge or intelligent design systems, the resulting designs
would end up in either just a mere copy and paste of an existing origami
pattern or an "origami inspired" design which is not using the properties
of origami in functional ways.
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.  
C04  Mar. 1 
[+]
Specialized origami design: Origami art, universal hinge patterns, fold and one cut. Guest Lecture: Chuck Hoberman 
[Notes]  [Slides]  
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. 

L05  [+]
Artistic origami design: sampling of representational
origami art; tree method and its use.
(guest lecture by Jason Ku) 
[Slides]  [Video] [Extra Video] 

This is a guest lecture by Jason Ku, president of OrigaMIT
(the MIT origami club), PhD student in mechanical engineering, and
prominent origami designer.
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 realworld 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.  
L06  [+]
Universal hinge patterns: box pleating, polycubes;
orthogonal maze folding. (first 25 minutes of video) OPTIONAL — NPhardness: introduction, reductions; simple foldability; crease pattern flat foldability; disk packing (for tree method). 
[Notes]  [Slides]  [Video] [Extra Video] 

This lecture covers two main topics:
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 NPhardness, and prove three origami problems NPhard:
 
L07  [+] Fold and one cut: history, straightskeleton method, diskpacking method, simple folds, higher dimensions, flattening polyhedra.  [Notes]  [Slides]  [Video] [Extra Video] 

This lecture is about my first work in computational origami: folding a piece of paper flat so that one complete straight cut makes a desired pattern of cuts (and resulting polygonal shapes). The problem has a long history (back to the 1700s) and possible applications to airbag folding through a problem called flattening. We'll see two different methods for this problem, each with connections to the tree method of origami design: the first generalizes the universal molecule to nonconvex polygons, but loses the ability to control the shadow tree; the second uses disk packing (but no rivers) and universal molecules for triangles and quadrangles. I'll also talk about a brand new result that started from this class three years ago: what shapes can you make only with simple folds?  
C05  Mar. 8 
[+]
Advanced origami: Pleat folding, curved creases. Linkage design: Kempe. Guest Lecture: Duks Koschitz 
[Notes]  [Slides]  
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 curvedcrease folding, with beautiful work; he was also an MIT student and professor. His work was recently acquired by MIT Museum and is being cataloged. 

L08  [+]
Pleat folding: “Hyperbolic paraboloid”,
circular pleat, selffolding origami,
plastic deformation and elastic memory;
triangulation, interval arithmetic; how paper folds between
creases, ruled surfaces, torsal, straight creases stay straight,
polygons stay flat; nonexistence.
Inflation: Teabag problem, inflating polyhedra. Curved creases: Recreating David Huffman's curvedcrease folding. 
[Notes]  [Slides]  [Video] [Extra Video] 

This lecture is primarily about pleat folding, specifically
the socalled “hyperbolic paraboloid” model common in origami
and originating at the Bauhaus in the late 1920s. Surprisingly,
this origami model does not exist: it's impossible to fold anything
nonflat with a crease pattern consisting of concentric squares and
diagonals. We'll prove this, using a new theory for how paper folds
in between creases, in particular showing that straight creases stay
straight when folded, and interior polygons stay flat when folded.
By contrast, we'll show how the “hyperbolic paraboloid” folds fine
after adding specific diagonal creases to the trapezoidal faces.
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.  
L09  [+]
Folding motions: folded states vs. motions;
universal foldability of polygonal paper. Linkages to sign your name: graphs vs. linkages vs. configurations, configuration space; Kempe Universality Theorem, original proof, bug, corrections, generalizations and strengthenings. 
[Notes]  [Slides]  [Video] [Extra Video] 

This lecture kicks off the beginning of linkage folding.
We'll segue from origami by thinking about folding motions of pieces of
paper, and prove that it's always possible to reach any folded state
of a polygonal piece of paper. How many extra creases do we need?
This unsolved question leads to problems in the linkagefolding domain.
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.  
C06  Mar. 15 
[+]
Rigidity: Generic, infinitesimal, tensegrity. Linkage universality: Carpenter's Rule Theorem. Guest Lecture: Tom Hull 
[Notes]  [Slides]  
Prof. Tom Hull is visiting from Western New England University, speaking about the mathematics of selffolding 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. 

L10  [+] Rigidity theory: Rigidity, generic rigidity, minimal generic rigidity, Henneberg characterization, Laman characterization, polynomialtime algorithm, convex polyhedra.  [Notes]  [Slides]  [Video] [Extra Video] 

This lecture is about rigidity theory, which is about telling
when a linkage can fold at all. This field goes back to mechanical
engineering of the 18th and 19th centuries, with applications to
structural engineering and architecture (getting buildings and
bridges to stand up), biology (understanding which parts of a protein
still move after folding up), and linkage folding itself (beyond just
“does it move at all?”, as we'll see in the next lecture).
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 (quadratictime) 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.  
L11  [+]
Rigidity theory: Infinitesimal rigidity, rigidity matrix. Tensegrity theory: tensegrities, equilibrium stress, duality, polyhedral lifting, MaxwellCremona Theorem. Locked linkages: Carpenter's Rule Theorem. 
[Notes]  [Slides]  [Video] [Extra Video] 

This lecture continues our tour through rigidity theory,
introducing two more big ideas: infinitesimal rigidity and
tensegrities. Infinitesimal rigidity is a nice way to capture the
generic case using linear algebra, and it nicely generalizes (and is
efficiently computable) in any dimension. Tensegrities (a term coined
by Buckminster Fuller) allow the addition of struts (which prevent
compression) and cables (which prevent expansion) in addition to bars
(which prevent both—which is what we've mostly been thinking about).
A nice special case of tensegrities are “spider webs”, which turn out
to relate to the algorithmic design of origami tessellations.
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”.  
C07  Mar. 22  [+] Linkage universality: Locked linkages and unfolding algorithms. Hinged dissections: Universality.  [Notes]  [Slides]  
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 selffolding robot from Science (which was his PhD work at Harvard). It should be fun! 

L12  [+] Locked linkages: Algorithms for unfolding 2D chains, pseudotriangulation, energy; rigid folding of singlevertex origami; locked trees, infinitesimally locked linkages, Rules 1 and 2; locked 3D chains, knitting needles.  [Notes]  [Slides]  [Video] [Extra Video] 

This lecture is about locked linkages. Continuing on from the Carpenter's Rule Theorem from last lecture, which says that 2D chains can't lock, we'll see three different algorithms for folding 2D chains. Each algorithm has varying levels of expansiveness, symmetry, and efficiency, with applications to 2D robotarm motion planning. We'll also see an application of a spherical version of the Carpenter's Rule Problem to rigid folding of singlevertex origami. Then we'll tour the world of locked 2D trees, which has had significant progress recently. To this end, I'll describe the extensive technology for proving 2D linkages to be locked. Finally we'll briefly look at locked 3D chains, which relates to protein folding.  
L13  [+] Hinged dissections: Locked and unlocked chains of planar shapes, adorned chains, slender adornments, slender implies not locked, Kirszbaun's Theorem, locked triangles with apex angle > 90°; existence of hinged dissections, refinement.  [Notes]  [Slides]  [Video] [Extra Video] 

This lecture is about chains of polygons, or other 2D shapes, connected together by hinges in 2D. These structures are classically called “hinged dissections”. On the foldability side, we'll see some surprisingly general situations, called “slender adornments”, where these chains cannot lock, building on the Carpenter's Rule Theorem and expansiveness (Lecture 11). We'll also see some examples that do lock, building on our theory of infinitesimally locked linkages and Rules 1 and 2 (Lecture 12). On the design side, we'll show that we can actually design hinged dissections that fold into any finite collection of desired polygonal shapes, using slender adornments to guarantee foldable motions.  
C08  Apr. 5  [+] Polyhedron unfolding.  [Notes]  [Slides]  
C08 description. TBD. 

L14  [+] Polyhedron unfolding: Edge unfoldings, general unfoldings, big questions, curvature, general unfolding of convex polyhedra, source unfolding, star unfolding, edgeunfolding special convex polyhedra, fewest nets, edgeununfoldable nonconvex polyhedra.  [Notes]  [Slides]  [Video] [Extra Video] 

This lecture begins our coverage of polyhedron (un)folding.
Specifically, we'll talk about how to cut open a polyhedral surface
into one piece without overlap so that that piece can be cut out of
sheet material and assembled into the 3D surface. What distinguishes
this field from origami is that we're not allowed to cover any part
of the surface more than once. Two of the biggest open problems in
geometric folding are here:
 
L15  [+]
Polyhedron unfolding: Vertex unfolding, facet paths,
generally unfolding orthogonal polyhedra, grid unfolding,
refinement, Manhattan towers, orthostacks, orthotubes, orthotrees. Polyhedron folding: Cauchy's Rigidity Theorem, Alexandrov's uniqueness of folding. 
[Notes]  [Slides]  [Video] [Extra Video] 

This lecture continues the theme of unfolding polyhedra,
and kicks off our coverage of folding polygons into polyhedra.
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.)  
C09  Apr. 12  [+] Polyhedron folding.  [Notes]  [Slides]  
C09 description. TBD. 

L16  [+] Polyhedron folding: Decision problem, enumeration problem, combinatorial problem, nonconvex solution, convex polyhedral metrics, Alexandrov gluings, Alexandrov's Theorem, BobenkoIzmestiev constructive proof, pseudopolynomial algorithm, ungluable polygons, perimeter halving, gluing tree, rolling belts.  [Notes]  [Slides]  [Video] [Extra Video] 

This lecture dives into the problem of folding polygons into polyhedra.
The focus here is on folding convex polyhedra, though
there is one nice result about the nonconvex case by Burago & Zalgaller.
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.  
L17  [+] Polyhedron folding: Combinatorial type of gluing, exponential upper and lower bounds for combinatorially distinct gluings, polynomial upper bound for polygons of bounded sharpness, dynamic program for edgetoedge gluing, including polynomialtime decision, exponentialtime dynamic program for general gluing; case studies of Latin cross, equilateral triangle, and square.  [Notes]  [Slides]  [Video]  
This lecture continues our discussion of gluing polygons up and folding them into convex polyhedra, namely, via Alexandrov gluings. Now we'll see algorithms to actually find Alexandrov gluings, as well as give good bounds on how many there can be. Then I'll describe a few case studies: the Latin cross, the equilateral triangle, and the square.  
C10  Apr. 19  [+] Specialized polyhedron folding. Protein folding.  [Notes]  [Slides]  
C10 description. TBD. 

L18  [+]
Polyhedron refolding: Dissectionlike open problem,
regular tetrahedron to box, Platonic solids to tetrahedra,
box to box, polycubes, orthogonal unfoldings with nonorthogonal foldings.
Smooth polyhedron folding: Smooth Alexandrov, Dforms, ribbon curves. Smooth polyhedron unfolding: Smooth prismatoids. Smooth origami: wrapping smooth surfaces with flat paper, Mozartkugel, contractive mapping, BuragoZalgaller Theorem (crinkling/crumpling), stretched path, stretched wrapping, source wrapping, strip wrapping, petal wrapping, comb wrapping, Pareto curve. 
[Notes]  [Slides]  [Video] [Extra Video] 

This lecture is a big collection of fun results related to
unfolding, refolding, and smooth folding:
 
L19  [+] Protein folding: Fixedangle linkages, tree, and chains; span; flattening; flatstate connectivity, disconnectivity of orthogonal partially rigid trees, connectivity of orthogonal open chains; locked fixedangle chains; producible protein (fixedangle) chains, ribosome, βproducible chains, helixlike canonical configuration, flat states are producible, producible states are connected.  [Notes]  [Slides]  [Video] [Extra Video] 

This lecture is about fixedangle linkages in 3D, which
have the constraint that the angles (in addition to the lengths)
must remain fixed at all times. Fixedangle linkages model the mechanics
of chemical bonds between atoms in a molecule. In particular, the backbone
of a biological protein is a fixedangle tree in this model, and can be
approximated by a fixedangle chain. We'll cover several results
about fixedangle linkages, all motivated by questions about protein folding:
 
C11  Apr. 26  [+] Protein folding.  [Notes]  [Slides]  
C11 description. TBD. 

L20  [+]
Protein folding: HP model of protein folding,
NPhardness and approximation, unique optimal foldings, protein design.
Interlocked 3D chains: Lubiw's problem, unlocking 2chains, unlocking two 3chains and 2chains, interlocking 3chains, interlocking 3chain with 4chain, interlocking 4chain with triangle, interlocking 3chain with quadrangle, topological vs. geometric arguments, rigid and fixedangle variations. 
[Notes]  [Slides]  [Video]  
This lecture continues our discussion on protein folding,
this time focusing on simple theoretical models of the forces, rather
than the mechanics, behind protein folding. In particular, we'll
see the HP model, a lattice model capturing the hydrophobia of
certain amino, which try to hide from the surrounding water.
Finding the optimal folding a given protein is NPcomplete, but
there are some decent constantfactor approximations, and it's also
not known whether protein design is similarly hard. We'll see one step
in the direction of design: guaranteeing a unique optimal folding.
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.  
C12  May 3  Student Presentations I  
C13  May 10  Student Presentations II  
Videography:  Martin Demaine  Equipment: Video shot with a Canon VIXIA HG21 camera using Manfrotto 701HDV Pro Fluid Video Mini Head on Manfrotto 055XPROB Aluminum Tripod Legs. Audio recorded using Countryman IsoMax E6 EarSet Microphone on camera using Sennheiser EW 112p G3 wireless microphone system. See our guide to recording video lectures. 
Editor:  Erik Demaine 