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

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.