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. |
[PDF] | [JNT] |
| 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. |
[PDF] | [JNT] |
| 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. |
[PDF] | [JNT] |
| 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. |
[PDF] | [JNT] |
| 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. |
[PDF] | [JNT] |
| 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. |
[PDF] | [JNT] |
| 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. |
[PDF] | [JNT] |
| 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. |
[PDF] | [JNT] |
| 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] |