6.885: Folding and Unfolding in Computational Geometry (Fall 2004)

Prof. Erik Demaine

These are rough, personal lecture notes handwritten by Erik Demaine used during lecture. Their primary purpose is for reading/review by students of the class. Accessibility

• Lecture 1: Introduction to the class; overview of topics and problems considered -- pages 1, 2, 3, 4, 5, 6
  • You can find out more about the morphing, stent, and space deployment applications in particular. [page 1]
  • There are Java applets for the Watt parallel motion and Peaucellier linkage. [page 2]
  • You can also view Kempe's How To Draw A Straight Line. [page 2]
  • There are several webpages about origami tessellations, including Andy Wilson's, Alex Bateman's, Helena Verrill's, and Chris Palmer's Shadowfolds,
    You can find some photos of David Huffman's curved folds at Xerox PARC art show and GRAFICA Obscura. [page 5]
  • For two examples of folding polygons into polyhedra, you can look at all possible gluings of the square, and at the Metamorphosis of the Cube video, which in particular shows different gluings of the standard cross unfolding of the cube. [page 6]

• Lecture 2: Linkages, configurations, configuration space, trace; Kempe Universality Theorem, his proof, the bug; topological universality; signing your name -- pages 1, 2, 3, 4, 5
  • You can view an applet of the square linkage example. [page 1]
  • You can view Kempe's related book, How To Draw A Straight Line. [page 2]
  • You can view applets for a contraparallelogram, multiplicators, and an additor. [page 3]
  • You can download the paper by Gao, Zhu, Chou, and Ge on polynomial bounds and algorithms for Kempe linkages and a generalization to 2D surfaces in 3D. [page 4]
  • You can view an applet signing the letter C. [page 5]

• Lecture 3: Rigidity theory, generic rigidity, minimal generic rigidity, Henneberg characterization, Laman characterization, polynomial-time algorithm -- pages 1, 2, 3, 4, 5, 6, 7
  • You can download the paper by Koiran, where the NP_R-hardness is via a small reduction from other results. [page 1]
  • Michael Thorpe is one of the people applying Laman conditions, studying the flexibility of proteins. In particular, I showed Figure 1 from this article showing the flexibility of the HIV protease with and without an inhibitor. [pages 5, 6]
  • You can download the paper by Jacobs and Hendrickson describing the pebble algorithm, and the paper by Hendrickson describing the bipartite-matching algorithm. [page 6]

• Lecture 4: Infinitesimal rigidity, tensegrities, stresses, duality, Maxwell-Cremona theorem, locked linkages, carpenter's rule theorem -- pages 1, 2, 3, 4
  • You can look at an example of Buckminster Fuller's tensegrity sculptures, the Sixty Strut Tensegrity Sphere.
    You can look at many of Kenneth Snelson's tensegrity sculptures on his webpage.
    George Hart has a webpage describing how to build your own tensegrity. [page 2]
  • You can view the paper proving the Carpenter's rule theorem. [page 4]

• Lecture 5: Algorithms for unfolding 2D chains, infinitesimally locked linkages, locked 3D chains (knitting needles), pocket flipping, Erdős-Nagy Theorem, deflations, flipturns -- pages 1, 2, 3, 4, 5
  • You can view the papers on each of the three algorithms: original ordinary differential equation, pseudotriangulations, and energy. [page 1]
  • You can view the paper by Alt, Knauer, Rote, and Whitesides proving PSPACE-hardness of deciding reachability between two configurations of a 2D tree or a 3D chain. [pages 2, 3]
  • You can view the paper about infinitesimally locked linakges. [page 2]
  • You can view the paper by Cantarella and Johnston and a related paper about locked 3D chains. [page 3]
  • You can view Godfried Toussaint's excellent survey on the Erdős-Nagy Theorem, its history, and related results. The proof presented here is based on the proof described in Godfried's paper, which in turn is based on Nagy's original proof. [page 4]
  • The large-flip example appears in this paper about locked 3D chains.
    A paper by Fevens, Hernandez, Mesa, Morin, Soss, and Toussaint covers deflations and the infinite deflation example.
    An applet by Christopher Gray demonstrates the infinite deflation example.
    Recent papers by Ahn, Bose, Czyzowicz, Hanusse, Kranakis, and Morin and by Aichholzer, Cortés, Demaine, Dujmović, Erickson, Meijer, Overmars, Palop, Ramaswami, and Toussaint cover flipturns. [page 5]

• Lecture 6: Paper folding: overview, definitions, connectivity, 1D flat foldability, 2D map folding -- pages 1, 2, 3, 4, 5
  • You can view the paper by Demaine, Devadoss, Mitchell, O'Rourke on definitions of folding and connectivity of the configuration space. The definition here is slightly different from the one presented in the paper, allowing more general pieces of paper and arbitrary dimension, and a cleaner noncrossing condition. [pages 2, 3]
  • You can view the paper by Arkin, Bender, Demaine, Demaine, Mitchell, Sethia, and Skiena on 1D flat foldability and 2D map folding. [pages 4, 5]

• Lecture 7: Fix for proof of Erdős-Nagy Theorem; characterizations of flat-foldable single-vertex crease patterns and mountain-valley patterns; continuous foldability of single-vertex patterns; linear-time algorithm for local foldability; NP-hardness of global foldability -- pages 1, 2, 3, 4, 5
  • Tom Hull's papers on The Combinatorics of Flat Folds: a Survey and Counting Mountain-Valley Assignments for Flat Folds cover several of these results. [pages 2, 3]
  • You can view a short abstract on continuous foldability of single-vertex origami. [page 4]
  • You can view the Bern and Hayes paper on local foldability and the complexity of global foldability. [pages 4, 5]

• Lecture 8: Silhouette folding and gift wrapping, universality, efficiency, seam placement, cube wrapping, checkerboard folding; tree method, margulis napkin problem -- pages 1, 2, 3, 4
  • You can view the Demaine, Demaine, and Mitchell paper on folding silhouettes and wrapping polyhedra. [pages 1, 2]
  • You can also view the Arkin, Held, Mitchell, Skiena paper on Hamiltonian refinement of triangulations. [page 2]
  • You can view Marc Kirschenbaum's diagrams of a seamless (1/5) 8-by-8 chessboard. [page 3]
  • You can download and play with Lang's TreeMaker (read the PDF file from version 4.0 for instructions) if you have a Mac. The main recommended reading is Lang's book Origami Design Secrets. Robert J. Lang Origami also has some information on the tree method (under Science / Tree Theory). [page 4]

• Lecture 9: Fold-and-cut problem: straight-skeleton method, disk-packing method. Flattening polyhedra. -- pages 1, 2, 3, 4, 5
  • The fold-and-cut page details some of the history, including scans from the Kan Chu Sen book. [page 1]
  • You can view the original paper introducing straight skeletons by Aichholzer, Aurenhammer, Alberts, and Gärtner. [page 1]
  • You can view the paper by Demaine, Demaine, and Lubiw describing the straight-skeleton method (sans dense spirality). [pages 1, 2, 3]
  • You can view the paper by Bern, Demaine, Eppstein, and Hayes describing the disk-packing method (somewhat simplified from the original version). [page 4]

• Lecture 10: Polyhedron (un)folding in general, polyhedron unfolding in particular: edge unfoldings, general unfoldings, main questions and results, curvature, source unfolding, star unfolding, ununfoldable polyhedra -- pages 1, 2, 3, 4, 5
  • You can watch the Metamorphosis of the Cube video. [page 1]
  • The paper by Bern, Demaine, Eppstein, Kuo, Mantler, and Snoeyink presents most of the general properties of unfoldings and cuttings, and the trivial ununfoldable polyhedron with boundary. [page 2]
  • You can view a paper about the star unfolding by Agarwal, Aronov, O'Rourke, and Schevon (a followup to the original Aronov and O'Rourke paper). [page 3]
  • You can view Schlickenrieder's diplom thesis. [page 4]
  • A paper by Biedl et al. presents the orthogonal ununfoldable polyhedra. The paper by Bern, Demaine, Eppstein, Kuo, Mantler, and Snoeyink presents the triangulated ununfoldable polyhedron. A paper by Branko Grünbaum presents another ununfoldable polyhedron and some additional conjectures about "unununfoldable" polyhedra. [page 5]

• Lecture 11: Vertex unfolding, unfolding orthogonal polyhedra; Cauchy's rigidity theorem, uniqueness of folding -- pages 1, 2, 3, 4, 5
  • You can view the vertex-unfolding paper. Another paper by Bartholdi and Goldsman established similar results but in a different setting. [pages 1, 2]
  • You can view the original Biedl et al. paper with grid unfoldings of orthotubes and general unfoldings of orthostacks. You can also view the recent Demaine, Iacono, and Langerman paper with grid vertex unfoldings of orthostacks. [page 3]

• Lecture 12: Flexible polyhedra, Bellows Theorem; folding polygons into polyhedra, gluings, convex polyhedral metrics, Aleksandrov's Theorem, Sabitov's algorithm, ungluable polygons -- pages 1, 2, 3, 4, 5
  • You can view illustrations of Bricard's flexible "octahedron", Connelly's flexible polyhedron, and Steffen's flexible polyhedron. You can view the paper proving the Bellows Conjecture. [page 1]
  • You can view the Fedorchuk and Pak paper on volume polynomials and algorithms for Aleksandrov's Theorem, which also summarizes Sabitov's work. [pages 1, 4]
  • You can view the Demaine, Demaine, Lubiw, O'Rourke paper about foldings of polygons into convex polyhedra. [page 5]

• Lecture 13: Perimeter halving, gluing trees, rolling belts, exponential number of gluings, dynamic-programming algorithm for edge-to-edge gluing -- pages 1, 2, 3, 4
  • You can view the Demaine, Demaine, Lubiw, O'Rourke paper about foldings of polygons into convex polyhedra. [pages 1, 2, 3]
  • You can view the original Lubiw and O'Rourke paper that studied efficient algorithms to find edge-to-edge gluings. [page 4]

• Lecture 14: Upper bounds on combinatorially distinct general gluings, bounded sharpness, dynamic-programming algorithm for enumerating gluings; Latin cross and square case studies; teabag problem. -- pages 1, 2, 3, 4, 5
  • See David Eppstein's teabag page and Andrew Kepert's teabag page. [page 5]

• Lecture 15: Protein folding: biochemistry background, mechanics vs. energetics, fixed-angle linkages, dihedral motion, locked proteins, span, flattening -- pages 1, 2, 3, 4, 5

• Lecture 16: Flat-state connectivity: partially rigid trees, orthogonal open chains, multiple pinned orthogonal chains -- pages 1, 2, 3, 4, 5

• Lecture 17: Producible protein (fixed-angle) chains: ribosome, β-producible chains, helix-like canonical configuration, canonicalization of producible chains, flat-state connectivity; HP model of protein-folding energetics. -- pages 1, 2, 3, 4, 5, 6

• Lecture 18: Tree method of computational origami design -- pages 1, 2, 3
  • You can view the slides in PDF format that supplement this lecture, and the paper on which this lecture is based, which appeared in SoCG'96.

• Lecture 19: Rigid origami -- pages 1
  • You can view slides from this lecture in PDF format.

• Lecture 20: More map folding: some-layers, one-layer, and all-layers simple folds; algorithms for all-layers case via suffixes and Karp-Rabin fingerprinting -- pages 1, 2, 3, 4, 5

• Lecture 21: Origami constructable numbers, straight edge and compass review, origami axioms, arithmetic, square roots, angle trisection, cube roots, characterization, relations to other construction tools -- pages 1, 2, 3, 4, 5, 6, 7

• Lecture 22: Interlocked 3D chains, Lubiw's problem -- pages 1, 2, 3, 4

• Lecture 23: Project Presentations I: Blaise Gassend, Michael Burr, Benjamin Hebert, Hank Hoffmann, Paul Stellman & Satoshi Takahashi -- pages 1, 2, 3

• Lecture 24: Project Presentations II: Tim Abbott & Reid Barton, Ariel Rideout & Ryan Williams, Toby Schachman, Steven Sivek, Michael Baym -- pages 1, 2, 3, 4, 5