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
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.
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.
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.
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.
Get the latest updates from
MIT Technology Review
Discover special offers, top stories, upcoming events, and more.