Skip to Content

Origami Crease Pattern Design Proved NP-Hard

Origamists have long suspected their art is computationally hard. Now they’ve proved it.

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: Circle Packing for Origami Design Is Hard

Keep Reading

Most Popular

AV2.0 autonomous vehicles adapt to unknown road conditions concept
AV2.0 autonomous vehicles adapt to unknown road conditions concept

The big new idea for making self-driving cars that can go anywhere

The mainstream approach to driverless cars is slow and difficult. These startups think going all-in on AI will get there faster.

biomass with Charm mobile unit in background
biomass with Charm mobile unit in background

Inside Charm Industrial’s big bet on corn stalks for carbon removal

The startup used plant matter and bio-oil to sequester thousands of tons of carbon. The question now is how reliable, scalable, and economical this approach will prove.

images created by Google Imagen
images created by Google Imagen

The dark secret behind those cute AI-generated animal images

Google Brain has revealed its own image-making AI, called Imagen. But don't expect to see anything that isn't wholesome.

AGI is just chatter for now concept
AGI is just chatter for now concept

The hype around DeepMind’s new AI model misses what’s actually cool about it

Some worry that the chatter about these tools is doing the whole field a disservice.

Stay connected

Illustration by Rose WongIllustration by Rose Wong

Get the latest updates from
MIT Technology Review

Discover special offers, top stories, upcoming events, and more.

Thank you for submitting your email!

Explore more newsletters

It looks like something went wrong.

We’re having trouble saving your preferences. Try refreshing this page and updating them one more time. If you continue to get this message, reach out to us at with a list of newsletters you’d like to receive.