Skip to Content
Uncategorized

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: arxiv.org/abs/1008.1224: Circle Packing for Origami Design Is Hard

Keep Reading

Most Popular

Large language models can do jaw-dropping things. But nobody knows exactly why.

And that's a problem. Figuring it out is one of the biggest scientific puzzles of our time and a crucial step towards controlling more powerful future models.

OpenAI teases an amazing new generative video model called Sora

The firm is sharing Sora with a small group of safety testers but the rest of us will have to wait to learn more.

Google’s Gemini is now in everything. Here’s how you can try it out.

Gmail, Docs, and more will now come with Gemini baked in. But Europeans will have to wait before they can download the app.

This baby with a head camera helped teach an AI how kids learn language

A neural network trained on the experiences of a single young child managed to learn one of the core components of language: how to match words to the objects they represent.

Stay connected

Illustration 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 customer-service@technologyreview.com with a list of newsletters you’d like to receive.