Select your localized edition:

Close ×

More Ways to Connect

Discover one of our 28 local entrepreneurial communities »

Be the first to know as we launch in new countries and markets around the globe.

Interested in bringing MIT Technology Review to your local market?

MIT Technology ReviewMIT Technology Review - logo

 

Unsupported browser: Your browser does not meet modern web standards. See how it scores »

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

29 comments. Share your thoughts »

Reprints and Permissions | Send feedback to the editor

From the Archives

Close

Introducing MIT Technology Review Insider.

Already a Magazine subscriber?

You're automatically an Insider. It's easy to activate or upgrade your account.

Activate Your Account

Become an Insider

It's the new way to subscribe. Get even more of the tech news, research, and discoveries you crave.

Sign Up

Learn More

Find out why MIT Technology Review Insider is for you and explore your options.

Show Me
×

A Place of Inspiration

Understand the technologies that are changing business and driving the new global economy.

September 23-25, 2014
Register »