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

Prof. Erik Demaine


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

Lecture 5 Video     [previous] [next]

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

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.

Download Video: 360p, 720p

Handwritten notes, page 1/7[previous page][next page][PDF]

Handwritten notes, page 1/7[previous page][next page][PDF]

Slides, page 1/20[previous page][next page][PDF]

http://​www.pnas.org/​content/​107/​28/​12441 / http://​www.pnas.org/​content/​suppl/​2010/​06/​25/​0914069107.DCSupplemental / http://​erikdemaine.org/​papers/​Matter_PNAS/​ (covered under the MIT Faculty Open-Access Policy)

Slides, page 1/20[previous page][next page][PDF]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The handwritten notes and slides should advance automatically. If you have any trouble with playback, email Erik.