Origami Crease Pattern Design Proved NP-Hard

Some 20 years or so, various individuals recognised that the problem of folding a square sheet of paper into an arbitrary 3D shape had many similarities to problems in computational geometry. These practitioners began developing algorithms that automatically generate the crease patterns that turn a flat sheet into an intricate shape of your choice. Thanks to this and the magical power of modern computing machines, origami is currently undergoing a technical and creative revolution.

But this new science of paper folding has lead to some entirely new conundrums. Having turned origami into a problem of computer science, it wasn’t long before origamists began asking themselves computer science-like questions. In particular, they want to know how computationally difficult origami actually is. Today, they have an answer thanks to the work of Robert Lang, one of the world leaders in computational origami, and a couple of his buddies: Erik Demaine at MIT, and Sándor Fekete at the University of Technology in Braunschweig, Germany.

The process of origami design is conceptually simple. Origamists begin with the shape to be recreated–a spider shape say. They then redraw this as a stick figure consisting, in this case, of a body and eight legs.

Origamists know that each extremity can be reproduced by folding a flap of paper in a particular way. So the key step in designing an origami spider is to find a way of folding a piece of paper so it that produces eight, suitably sized and spaced flaps, one for each leg. After that, it’s just a question of shaping the flaps to make them look leg-shaped, a relatively straight forward task.

The experts in this field have long suspected the process of turning a stick figure into a crease pattern is computationally intractable. Now Lang and co prove that this intuition is correct by showing that the process is NP-hard. So it is much harder to devise a crease pattern that produces a spider than it is to check that a given solution is correct (ie by folding it into a spider).

They’ve done this using the standard trick of showing that the problem of origami is equivalent to another problem that is already known to be NP-hard, in this case the problem of packing circles into a given space.

At first glance, it’s hard to see how origami can be related to circle packing but actually there’s a straightforward link. Think back to the stick figure of the spider. Then draw a circle around each node with a radius that is half the distance to another node. The problem of origami, finding a way of positioning these nodes so that the paper can be folded in such a way that each node represents a vertice in the final shape, is then equivalent to finding an optimal way of packing the spheres.

While the proof will come as little surprise, it does have an interesting corollary. In the course of making this breakthrough, Lang and co show that any set of circles with a total area of 1 can be packed into a square of size 8/pi = 2.546… An origamic triumph by anybody’s standards.

Ref: arxiv.org/abs/1008.1224: Circle Packing for Origami Design Is Hard