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,
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]|