6.885: Geometric Folding Algorithms: Linkages, Origami, Polyhedra (Fall 2007)

Prof. Erik Demaine       TA: Nadia Benbernou

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

Erik's Lecture Notes

These are rough, personal lecture notes handwritten by Erik Demaine and used during lecture, intended primarily for students of the class.

The notes are currently available in two formats: Adobe PDF and Windows Journal (JNT). The former is easily portable, viewable, printable, etc. The latter is useful for annotatation by Windows Tablet PC users.

L1 Sept. 5 Overview of the entire class: Topics and problems considered. [PDF] [JNT]
L2 Sept. 10 Linkages to sign your name: Basic terminology, graphs vs. linkages vs. configurations, configuration space, Kempe Universality Theorem, original proof, bug, corrections, generalizations and strengthenings. [PDF] [JNT]
L3 Sept. 12 Rigidity theory: Rigidity, generic rigidity, minimal generic rigidity, Henneberg characterization, Laman characterization, polynomial-time algorithm. [PDF] [JNT]
L4 Sept. 17 Rigidity theory: Infinitesimal rigidity, rigidity matrix.
Tensegrity theory: tensegrities, equilibrium stress, duality, polyhedral lifting, Maxwell-Cremona Theorem.
Locked linkages: Carpenter's Rule Theorem.
L5 Sept. 19 Locked linkages: Algorithms for unfolding 2D chains, locked trees, infinitesimally locked linkages, locked 3D chains (knitting needles), flips, deflations, flipturns, pops, popturns. [PDF] [JNT]
L6 Sept. 26 Paper folding: Definitions, connectivity of configuration space, crease pattern, mountain-valley assignment.
Flat foldability: 1D characterization, 2D map folding, simple folds, NP-hardness for orthogonal maps.
L7 Oct. 1 Flat foldability: Single-vertex crease patterns, characterizations of flat-foldable crease patterns and mountain-valley patterns, combinatorics of the latter, continuous foldability without extra creases, spherical carpenter's rule problem, local flat foldability is easy, global flat foldability is NP-hard. [PDF] [JNT]
L8 Oct. 3 Origami design: Folding any shape (silhouette or gift wrapping), strip folding, pseudo-efficiency, seam placement, cube wrapping, checkerboard folding; Lang's tree method, uniaxial base, active path, rabbit-ear molecule, universal molecule, Margulis Napkin Problem. [PDF] [JNT]
L9 Oct. 10 Origami design: Fold and one cut, history, straight-skeleton method, disk-packing method, higher dimensions, flattening polyhedra. [PDF] [JNT]
L10 Oct. 15 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. [PDF] [JNT]
L11 Oct. 17 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.
L12 Oct. 22 Polyhedron folding: Decision problem, enumeration problem, combinatorial problem, convex polyhedral metrics, Alexandrov gluings, Alexandrov's Theorem, Bobenko-Izmestiev algorithm, ungluable polygons, perimeter halving, gluing tree, rolling belts. [PDF] [JNT]
L13 Oct. 24 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 and square. [PDF] [JNT]
L14 Oct. 29 Polyhedron refolding: Dissection-like open problem, Hirata's regular tetrahedron to box, box to box, orthogonal polygons with nonorthogonal foldings.
Smooth polyhedron folding: Smooth Alexandrov, D-forms, ribbon curves.
Smooth origami: curved-crease origami, developable surfaces, generating lines, osculating plane; 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.
L15 Oct. 31 Smooth polyhedron unfolding: Smooth prismatoids, flat case, nonintersection of ribs, mutual tangency, maximum rib displacement.
Flexible polyhedra: convex polyhedra are rigid, square-bottom paper bag, generic case, Bricard octahedron, Connelly polyhedron, Steffen polyhedron, Bellows Theorem, volume polynomials.
Protein folding: Biochemistry, DNA, RNA, proteins, ribosome, mechanics, energetics.
L16 Nov. 5 Protein folding: Fixed-angle linkages, tree, and chains; major problems; locked proteins; flattening is weakly NP-hard; flat min/max span are weakly NP-hard; equiangular max span is polynomial in 2D and 3D. [PDF] [JNT]
L17 Nov. 7 Protein folding: Flat-state connectivity, summary of results; disconnectivity of orthogonal partially rigid trees, multiple pinned partially rigid orthogonal open chains, and orthogonal graphs; connectivity of orthogonal open chains and multiple pinned orthogonal open chains. [PDF] [JNT]
L18 Nov. 14 Protein folding: Producible protein (fixed-angle) chains, ribosome, β-producible chains, bound on turn angles α, helix-like canonical configuration, canonicalization of producible chains, flat-state connectivity; HP model of protein-folding energetics, NP-hardness and approximation, unique optimal foldings, protein design. [PDF] [JNT]
L19 Nov. 19 Flips and friends: Pockets, flips, “Erdős-Nagy Theorem”, false and correct proofs; flipturns, orthogonal bound, general bound.
Polyhedron folding: Constructive proof vs. algorithm, geodesic Delaunay triangulation.
L20 Nov. 25 Linkage folding: Locked and unlocked chains of planar shapes, adorned chains, adornments, slender adornments, slender implies not locked, symmetric case, Kirszbaun's Theorem, locked triangles with apex angle > 90°, simplification rules, stress argument; locked tree arguments. [PDF] [JNT]
L21 Nov. 27 Linkage folding: Interlocked 3D chains, Lubiw's problem, unlocking 2-chains, unlocking two 3-chains and 2-chains, interlocking 3-chains, interlocking 4-chain with triangle, interlocking 3-chain with quadrangle, interlocking 3-chain with 4-chain, topological vs. geometric arguments, rigid and fixed-angle variations. [PDF] [JNT]
L22 Dec. 3 Linkage folding: Self-touching Carpenter's Rule Theorem, combinatorial definition vs. limit definition, trouble with limits, global annotation idea, Ord, topological argument.
Applications: Reconfigurable robotics, programmable matter, nanomanufacturing, self-(re)assembly, hinged dissections, DNA origami, robotic paper.
Folding puzzles: Survey.
L23 Dec. 3 Paper folding: [Guest lecture by Tom Hull] Origami constructable numbers, straight edge and compass, basic origami operations, angle trisection, solving cubic equations, Lill's method, pushing the limits. Configuration space of flat-foldable single-vertex crease patterns.
L24 Dec. 10 Student presentations: Po-Ru Loh; David Charlton; Hoda Bidkhori; Amy Wibowo; Edwin Chen; Zach Abel; Duks Koschitz. [PDF] [JNT]
L25 Dec. 12 Student presentations: Greg Price; Aviv Ovadya; Katherine Romer; Joy Ebertz; Yoyo Zhou; Yaa-Lirng Tu; Andrea Hawksley, Shelly Manber, and Omari Stephens; Simon Kim. [PDF] [JNT]