[Erik holding a box-pleated MIT]
sample frame from lecture video (L06)

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

Prof. Erik Demaine       TA: Jayson Lynch


[Home] [Problem Sets] [Project] [Lectures] [Problem Session Notes] [Accessibility]

Video Lectures

Lxx indicate video lectures from Fall 2010.
Cxx indicate class sessions / contact hours.
L01 optional Overview of the entire class: Topics and problems considered.
OPTIONAL — L01 can be skipped, though it gives a more detailed overview of the class than C01.
[Notes] [Slides] [Video]
C01 Sept. 6 Overview of the class: Inverted lecture format, sample topics and problems considered. [Notes] [Slides] [Video]
L02 Sept. 10

[+] Origami intro: Piece of paper, crease pattern, mountain-valley assignment.
Universality: Folding any shape (silhouette or gift wrapping).
Simple folds: 1D flat-foldability characterization, 2D map-folding algorithm.

[Notes] [Slides] [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 well-studied 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 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.

C02 Sept. 11

[+] Origami intro: Origami alphabet, higher dimensions.
Universality: Terminology history, practical strip folding, pseudopolynomial bounds, seam placement, hide gadget via simple folds?
Simple folds: Metal/wood/plastic motivation, definition, examples, linear-time algorithm, extra creases.

[Notes] [Slides] [Video]
This class is structured around the many excellent questions that students asked and suggestions they made. There are so many that I've marked a few highlights with stars:
  • ★ Actual folding (we'll fold the numerals 6, 8, 4, 9 from an origami alphabet!)
  • Some history of where a few terms come from.
  • Practical examples of strip folding.
  • Pseudopolynomial bounds on strip folding: what they are and what's (un)known.
  • Seam placement (some skipped content in L02's notes)
  • ★ Open problem about simply folding the hide gadget: let's solve it together!
  • Motivation for simple folds: metal/wood/plastic bending
  • Definition of simple folds: more precise
  • Examples of flat-foldable vs. mingling 1D mountain-valley patterns
  • ★ Algorithm for testing 1D flat foldability in linear time (new -- simpler than textbook!)
  • Making any mountain-valley pattern flat foldable by adding extra creases
  • Higher-dimensional folding
L03 Sept. 12

[+] Single-vertex crease patterns: Characterizations of flat-foldable crease patterns and mountain-valley patterns, combinatorics of the latter, local flat foldability is easy.
Tree method of origami design: Introduction, uniaxial base, demo.

[Notes] [Slides] [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 single-vertex crease patterns and mountain-valley 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 Sept. 13

[+] Single-vertex crease patterns: Linear-time algorithm, local foldability examples, T-shirt folding, higher dimensions, why flat foldability?

[Notes] [Slides] [Video]
This class addresses these questions/comments about Lecture 3 (and Lecture 2):
  • How can we quickly determine whether a single-vertex mountain-valley pattern is flat foldable? We'll also cover the algorithm for 1D flat folding that we didn't have time to cover in Class 2.
  • Examples of how the local foldability algorithm works.
  • T-shirt folding (for fun)
  • Higher-dimensional flat folding (what little is known)
  • Why do we study flat foldability? Art (e.g. tessellations), practicality (compactness e.g. airbags), and mathematics (e.g. rigid foldability).
L04 Sept. 17

[+] Efficient origami design: Tree method, TreeMaker, uniaxial base, active path, rabbit-ear molecule, universal molecule, Margulis Napkin Problem; cube folding, checkerboard folding; Origamizer, watertight, tuck proxy.

[Notes] [Slides] [Video]
This lecture is all about efficient origami design. We saw in Lecture 2 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 3. 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 5). 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.

C04 Sept. 18

[+] Efficient origami design: Uniaxial, TreeMaker and Origamizer in practice, box-pleating tree method, tree method triangulation, universal molecule, gift wrapping, checkerboard gadgets, Origamizer software vs. mathematics, vertex/edge tucking molecules, Voronoi diagrams.

[Notes] [Slides] [Video]
This class covers several additional details about Lecture 4 (efficient origami design):
  • How is complex origami design we've seen uniaxial?
  • How are TreeMaker and Origamizer used in practice?
  • Box-pleating version of the tree method from Origami Design Secrets (2nd edition)
  • Triangulation algorithm for the tree method
  • Universal molecule example
  • Gift-wrapping problems are still open
  • How to fold the more efficient checkerboard
  • How the Origamizer software works
  • How the guaranteed-correct Origamizer algorithm is more complicated
L05 Sept. 19

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

[Slides] [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 4 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.

C05 Sept. 20

[+] Artistic origami design: Jason Ku designs, other materials (dollars, cardboard, hydro, metal, polypropylene), tessellations, Tess, connected cranes, modular origami, business card cubes.

[Notes] [Slides] [Video]
This class covers even more examples of artistic origami design:
  • Origami designs by Jason Ku (Lecture 5's guest lecturer)
  • Different materials: dollar bills, cardboard, Hydro-Folding, sheet metal, and polypropylene (a type of plastic)
  • Tessellations: folding in a repeated pattern
  • Tess, software for designing certain tessellations
  • Connected cranes, an old Japanese tradition of folding multiple cranes from a slit sheet of paper
  • Modular origami: geometric forms from multiple repeated units
  • Business card cube folding (hands on!)
L06 Sept. 24

[+] Architectural Origami: Origamizer, Freeform Origami, Rigid Origami Simulator, cylindrical origami, thick origami
(guest lecture by Tomohiro Tachi)

[Slides] [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.

C06 Sept. 25

[+] Architectural Origami: Origamizer, Freeform Origami, Rigid Origami Simulator

[Notes] [Slides] [Video]
This class provides some extra details related to Tomohiro Tachi's software suite:
  • Hands-on folding of simple Origamizer example
  • Example of nonconvex vertex in Origamizer
  • Demo of Freeform Origami: simulation and design modes
  • Geometric constraints in Rigid Origami Simulator, Freeform Origami, and Origamizer
  • Nonlinear constraint solution (briefly)
  • Why NP-completeness matters less here
  • Automatic folding via robots and Printed Circuit MicroElectricalMechanical Systems (PC-MEMS)
  • Open problems in rigid origami
  • Paper shopping bag folding
L07 Sept. 26

[+] Universal hinge patterns: box pleating, polycubes; orthogonal maze folding.
NP-hardness: introduction, reductions; simple foldability; crease pattern flat foldability; disk packing (for tree method).

[Notes] [Slides] [Video]
This lecture covers two main topics:

First, continuing our theme from Lecture 4 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.
C07 Sept. 27

[+] Universal hinge patterns: box-pleating history; maze-folding prints.
NP-hardness: simple foldability; crease pattern flat foldability.

[Notes] [Slides] [Video]
This class starts with some artistic examples related to the two universality results covered in Lecture 7: box pleating and maze folding.

Second, we review the NP-hardness proofs from Lecture 7:

  • What does hardness really mean?
  • Details of the simple fold hardness proof
  • Details of the flat foldability hardness proof
  • Extension to when given the mountain-valley assignment

Finally, we cover a new (this year) result: 2 × n map folding can be solved in polynomial time. (m × n map folding remains unsolved.)

L08 Oct. 1

[+] Fold and one cut: history, straight-skeleton method, disk-packing method, simple folds, higher dimensions, flattening polyhedra.

[Notes] [Slides] [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?
C08 Oct. 2

[+] Fold and one cut: software, scissor vs. mathematical cuts, tree folding, density, examples, how many disks, comparison to tree method, continuous flattening.

[Notes] [Slides] [Video]
This class describes several additional details about fold-and-cut:
  • Software:
    • David Benjamin and Anthony Lee's 6.849 Fall 2010 project (skeleton method)
    • JOrigami (disk-packing method)
  • Skeleton method:
    • Odd-degree vertices are possible with mathematical cuts, but not scissor cuts.
    • Two scissor cuts can (usually) simulate mathematical cuts.
    • Correspondence between linear corridors and shadow tree
    • Correspondence between tree folding and origami folding
    • Why dense configurations should happen only with probability 0
    • Comparison to tree method
  • Examples by past students
  • A magic trick
  • Disk-packing method:
    • Correspondence between disk packing and triangle/quad decomposition
    • How many disks are needed by a disk packing?
    • Comparison to tree method
    • Open problem with curved cuts
    • Continuous flattening: convex polyhedra now solved
    • Comparison to tree method
  • Paper cutting art
L09 Oct. 3

[+] Pleat folding: “Hyperbolic paraboloid”, circular pleat, self-folding 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 curved-crease folding.

[Notes] [Slides] [Video]
This lecture is primarily about pleat folding, specifically the so-called “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.

C09 Oct. 4

[+] Pleat folding: triangulated hypars, smoothness, normals, mathematical vs. real paper, pleat folding algorithms, hypar folding.

[Notes] [Slides] [Video]
This class consists of three parts: review, new material, and real folding.

For review, we cover some open problems about triangulated hypars, define smoothness (Ck), detail why uncreased polygonal regions of paper must be flat in 3D (normal arguments), and discuss how real paper might differ from mathematical paper.

For new material, we cover algorithms for optimally folding specified M/V patterns by a sequence of simple folds and unfolds. Specifically, we'll see that the patterns MMM... and MVMV... can be folded using O(lg2 n) folds, and require Ω(lg2 n / lg lg n) folds, while most patterns require Θ(n / lg n) folds.

For real folding, we will make (nonexistent) square hypars and assemble them into a hyparhedron sculpture.

L10 Oct. 10

[+] 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]
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 linkage-folding 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.

C10 Oct. 11

[+] Folding motions: trouble with holes.
Linkages to sign your name: sliding joints, contraparallelogram bracing, higher dimensions, semi-algebraic sets, splines.
Geometric construction: straight edge and compass, origami axioms, angle trisection, cube doubling.

[Notes] [Slides] [Video]
This class addresses the following questions:
  • Why paper with holes makes it hard to convert folded states to folding motions
  • How to simulate sliding joints with regular linkages
  • How the contraparallelogram gets braced (and why)
  • Kempe Universality Theorem in higher dimensions
  • Drawing semi-algebraic sets, e.g., splines, by taking intersections and unions of constructions

In addition, we cover the new topic of geometric construction via origami axioms, mentioned briefly at the end of Lecture 10. Single-fold origami can solve all cubic equations, unlike straight edge and compass which can solve (only) all quadratic equations. Two-fold origami can e.g. quintisect an angle, while n-fold origami can solve any polynomial.

We will also assemble our (nonexistent) square hypars from Class 9 and assemble them into a hyparhedron sculpture.

L11 Oct. 15

[+] Rigidity theory: Rigidity, generic rigidity, minimal generic rigidity, Henneberg characterization, Laman characterization, polynomial-time algorithm, convex polyhedra.

[Notes] [Slides] [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 (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.

C11 Oct. 16

[+] Rigidity theory: Pebble algorithms, rigid component decomposition, body-and-bar framework, angular rigidity, 5-connected double bananas.

[Notes] [Slides] [Video]
This class focuses on one main question: how exactly and why does that pebble algorithm detect Laman's condition for minimal generic rigidity? We'll start with a simpler version of the algorithm that tests whether every k vertices induce at most 2k edges, and then extend to the needed 2k − 3 condition. Then I'll mention several extensions:
  • Decomposing any graph into minimally rigid components and redundant edges
  • Body and bar (and hinge) frameworks
  • Angular constraints between lines and planes, or between bodies
Finally, we'll see that the tricky 3D double bananas example, and indeed any graph in 3D, can be extended to be 5-connected while preserving Laman and generic flexibility.
L12 Oct. 17

[+] Rigidity theory: Infinitesimal rigidity, rigidity matrix.
Tensegrity theory: tensegrities, equilibrium stress, duality, polyhedral lifting, Maxwell-Cremona Theorem.
Locked linkages: Carpenter's Rule Theorem.

[Notes] [Slides] [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”.

C12 Oct. 18

[+] Tensegrities: dot products, springs, software, sculpture.
Project discussion.

[Notes] [Slides] [Video]
This class addresses a few topics about rigidity/tensegrity:
  • More intuition for the dot-product condition of infinitesimal rigidity.
  • Why use springs to construct bars?
  • More examples of tensegrity sculpture
  • Tomohiro Tachi's Freeform Tensegrity software
  • Make your own tensegrity following George Hart's instructions
The focus is then an improvised discussion with everyone about their ideas for projects. We will discuss what's known/been done on specific problems, brainstorm what would be most interesting for a project, etc.
L13 Oct. 22

[+] Locked linkages: Algorithms for unfolding 2D chains, pseudotriangulation, energy; rigid folding of single-vertex origami; locked trees, infinitesimally locked linkages, Rules 1 and 2; locked 3D chains, knitting needles.

[Notes] [Slides] [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 robot-arm motion planning. We'll also see an application of a spherical version of the Carpenter's Rule Problem to rigid folding of single-vertex 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.
C13 Oct. 23

[+] Locked linkages: Why expansiveness, energy algorithm correctness, pointed pseudotriangulations (combinatorics, rigidity, universality, expansiveness, extremeness), linear equilateral trees can't lock, unfolding 4D chains.

[Notes] [Slides] [Video]
This class covers several interesting results about pointed pseudotriangulations:
  • Their original use for polygon ray shooting data structures.
  • Their (fixed) number of edges and faces (in contrast to triangulations).
  • Their minimal generic rigidity
  • Every planar minimally generically rigid graph can be drawn as a pointed pseudotriangulation (a kind of universality)
  • Why they work as an algorithm for the Carpenter's Rule Theorem: they have expansive motions after removing a convex-hull edge. (In particular, we'll review some lemmas from CDR.)
  • In fact, these expansive motions are the “extreme rays” (edges) of the cone of all expansive motions.

In addition, we cover the following questions and results:

  • Why do we use expansiveness? Both convenience and mathematical power.
  • Why can't the energy algorithm get stuck in a local minimum?
  • New result: linear equilateral trees can't lock
  • Old result: 4D (and higher-dimensional) open chains can't lock
L14 Oct. 24

[+] 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]
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 10). We'll also see some examples that do lock, building on our theory of infinitesimally locked linkages and Rules 1 and 2 (Lecture 11). 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.
C14 Oct. 25

[+] Hinged dissections: animations, polyform inductive construction, rectangle to rectangle, furniture, pseudopolynomial construction, 3D, Dehn invariant.

[Notes] [Slides] [Video]
This lecture covers four additional results:
  • How polyform (polyomino, polyiamond, polyhex, polycube, etc.) hinged dissection works
  • How rectangle-to-rectangle (nonhinged) dissection works
  • How we obtain a pseudopolynomial bound on hinged dissection
  • How (nonhinged) dissection works in 3D and 4D: the Dehn invariant
Along the way, we'll see some fun examples of animation and furniture.
L15 Oct. 31

[+] Polyhedron unfolding: Edge unfoldings, general unfoldings, big questions, curvature, general unfolding of convex polyhedra, source unfolding, star unfolding, edge-unfolding special convex polyhedra, fewest nets, edge-ununfoldable nonconvex polyhedra.

[Notes] [Slides] [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:
  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.
I'll describe the various attacks and partial results toward solving the first problem, as well as the reverse situations where we know much more: general unfolding of convex polyhedra and edge unfolding of general polyhedra.
C15 Nov. 1

[+] Polyhedron unfolding: Handles, holes, ridge trees; sun unfolding; zipper unfolding; more ununfoldable polyhedra; NP-completeness of edge unfolding; band unfolding; continuous blooming.

[Notes] [Slides] [Video]
This class covers five types of unfoldings:
  • Sun unfolding: A new generalization of the source unfolding that also incorporates elements of the star unfolding. It provably doesn't overlap. (Non)overlap of a dual version, which generalizes the star unfolding, remains an open problem.
  • Zipper unfolding: A new type of unfolding where the cutting forms a path. We have several specific examples and counterexamples of zipper edge unfoldings, but it remains open whether all convex polyhedra have general zipper unfoldings.
  • Edge-ununfoldability: We show several other edge-ununfoldable examples, the smallest of which has 13 faces, which is conjectured optimal. More generally, deciding whether a topologically convex orthogonal polyhedron has an edge unfolding is NP-complete. Pepakura's brute-force heuristics do decently in practice.
  • Band unfolding: A brief overview of how the side band of a prismatoid unfolds (even continuously blooms) without overlap. Attaching the top and bottom faces remains an open problem.
  • Continuous blooming: We cover two ways to continuously unfold any convex polyhedra. First, any unfolding can be refined and then bloomed, by making its dual Hamiltonian and sequentially unrolling. Second, the source unfolding blooms as is, by following a postorder traversal. Many open problems remain.
The class also address a few specific questions:
  • What's the formal definition of a handle?
  • Why can't unfoldings of convex polyhedra have holes? (Gauss-Bonnet Theorem)
  • Why are polyhedron vertices leaves of the ridge tree?
L16 Nov. 5

[+] 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]
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.)

C16 Nov. 6

[+] Polyhedron unfolding: Topologically convex vertex-ununfoldable polyhedron; unfolding orthogonal polyhedra with quadratic refinement.

[Notes] [Slides] [Video]
This class covers two new results about unfolding, one negative and one positive:

We'll also briefly discuss:

  • Why vertex unfoldings are so far “linear”
  • Why vertex unfoldings revisit vertices
  • Whether orthogonal unfoldings are practical
  • Whether other lattice polyhedra can be unfolded
  • Whether Cauchy's Rigidity Theorem is obvious
L17 Nov. 7

[+] Polyhedron folding: Decision problem, enumeration problem, combinatorial problem, nonconvex solution, convex polyhedral metrics, Alexandrov gluings, Alexandrov's Theorem, Bobenko-Izmestiev constructive proof, pseudopolynomial algorithm, ungluable polygons, perimeter halving, gluing tree, rolling belts.

[Notes] [Slides] [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.

C17 Nov. 8

[+] Polyhedron folding: Pita forms, D-forms, seam forms, convex hull and crease properties, rolling belts, Burago-Zalgaller folding into nonconvex polyhedra.

[Notes] [Slides] [Video]
This class focuses on D-forms (introduced by artist Tony Wills) and related constructions called pita forms and seam forms:
  • Pita forms were demonstrated in Lecture 17: take a convex polygon or curved shape and glue up two halves of its perimeter to make a convex surface.
  • D-forms extend this to gluing together two convex polygons or curves.
  • Seam forms further generalize to arbitrarily many, not necessarily convex polygons, but still require Alexandrov's Theorem to apply (actually a smooth version called Alexandrov-Pogorelov).

We'll make physical D-forms and prove two neat properties about them (which originate from a final project in this class from 2007). We'll also briefly review rolling belts, the implementation of Bobenko-Izmestiev's Alexandrov construction, and Burago-Zalgaller's folding of any polygon with any gluing into a nonconvex polyhedron [O'Rourke 2010; Spring 2005].

L18 Nov. 12

[+] 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 edge-to-edge gluing, including polynomial-time decision, exponential-time 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.
C18 Nov. 13 Watch origami documentary Between The Folds.
L19 Nov. 14

[+] Polyhedron refolding: Dissection-like open problem, regular tetrahedron to box, Platonic solids to tetrahedra, box to box, polycubes, orthogonal unfoldings with nonorthogonal foldings.
Smooth polyhedron folding: Smooth Alexandrov, D-forms, ribbon curves.
Smooth polyhedron unfolding: Smooth prismatoids.
Smooth origami: wrapping smooth surfaces with flat paper, Mozartkugel, contractive mapping, Burago-Zalgaller Theorem (crinkling/crumpling), stretched path, stretched wrapping, source wrapping, strip wrapping, petal wrapping, comb wrapping, Pareto curve.

[Notes] [Slides] [Video]
This lecture is a big collection of fun results related to unfolding, refolding, and smooth 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
The last section has practical applications to computational confectionery, reducing the material usage in wrappings of spherical chocolates such as Mozartkugel. Yum!
C19 Nov. 15

[+] Polyhedron refolding: Fractal unfolding, three boxes, flat boxes.
Kinetic sculpture: Theo Jansen's Strandbeests, Arthur Ganson.

[Notes] [Slides] [Video]
This class starts with some updates on common unfoldings:

Then, as a transition back to linkage folding (the next two lectures), we cover the beautiful leg mechanism of Theo Jansen's Strandbeests, and briefly review some of Arthur Ganson's kinetic sculptures.

L20 Nov. 19

[+] Protein folding: Fixed-angle linkages, tree, and chains; span; flattening; flat-state connectivity, disconnectivity of orthogonal partially rigid trees, connectivity of orthogonal open chains; locked fixed-angle chains; producible protein (fixed-angle) chains, ribosome, β-producible chains, helix-like canonical configuration, flat states are producible, producible states are connected.

[Notes] [Slides] [Video]
This lecture is about fixed-angle linkages in 3D, which have the constraint that the angles (in addition to the lengths) must remain fixed at all times. Fixed-angle linkages model the mechanics of chemical bonds between atoms in a molecule. In particular, the backbone of a biological protein is a fixed-angle tree in this model, and can be approximated by a fixed-angle chain. We'll cover several results about fixed-angle linkages, all motivated by questions about protein folding:
  • 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.
A lot is known about each question, though many problems remain open.
L21 optional

[+] Protein folding: HP model of protein folding, NP-hardness and approximation, unique optimal foldings, protein design.
Interlocked 3D chains: Lubiw's problem, unlocking 2-chains, unlocking two 3-chains and 2-chains, interlocking 3-chains, interlocking 3-chain with 4-chain, interlocking 4-chain with triangle, interlocking 3-chain with quadrangle, topological vs. geometric arguments, rigid and fixed-angle variations.
OPTIONAL — questions will be answered during C20.

[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 NP-complete, but there are some decent constant-factor 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.

C20 Nov. 20

[+] 3D linkage folding: ribosomes, HP protein folding NP-hardness, flattening is strongly NP-hard, flips, flipturns, deflations, pops, popturns.
This class covers both L19 and L21.

[Notes] [Slides] [Video]
This class opens with a discussion about the class as a whole, and how the experimental split into video lectures + live classes worked out.

Second, we address a few questions concerning:

  • Equilateral vs. equiangular vs. obtuse locked 3D chains
  • The shape of the ribosome
  • HP protein folding NP-hardness proofs

Third, we cover a new result: Flattening fixed angle chains (and min/max flat span) are strongly NP-hard [Demaine & Eisenstat 2011].

Fourth, we cover a fun series of results on polygon (closed chain) reconfiguration via flips, flipturns, deflations, pops, and popturns. [More detail can be found in 2010's Lecture 21.]

C21 Nov. 27 Student Presentations I
C22 Nov. 29 Student Presentations II
C23 Dec. 4 Student Presentations III
C24 Dec. 11 Student Presentations IV


Credits

Videography: Martin Demaine
Jayson Lynch
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 112-p G3 wireless microphone system. See our guide to recording video lectures.
Editor: Erik Demaine
Subtitles: OCW