Back in 1999, Erik Demaine was a PhD student who created an algorithm that determined the folding patterns necessary to turn a piece of paper into any 3D shape. However, the algorithm was far from perfect, often resulting in an inefficient final product with many visible seams. Eighteen years later Demaine, now a professor of electrical engineering and computer science at MIT, has completed his quest to create a universal algorithm for folding origami shapes with the smallest number of seams possible.
"In 1999, we proved that you could fold any polyhedron, but the way that we showed how to do it was very inefficient," Demaine says. "[The original algorithm is] efficient if your initial piece of paper is super-long and skinny. But if you were going to start with a square piece of paper, then that old method would basically fold the square paper down to a thin strip, wasting almost all the material."
Alongside Tomohiro Tachi from the University of Tokyo, Demaine will present the new algorithm at the Symposium on Computational Geometry in July that avoids this problem. The result is an incredibly complex algorithm that can take any inputed 3D structure and design the crease patterns needed to reproduce the shape as a paper polyhedron.
A pioneer of computational origami, Robert Lang, says this 20-year-long challenge has been difficult, but Demaine finally put all the algorithmic pieces of the puzzle together.
"Along the way, there have been several nice demonstrations of pieces of the puzzle: an algorithm to fold any shape, but not very efficiently; an algorithm to efficiently fold particular families of tree-like shapes, but not surfaces; an algorithm to fold trees and surfaces, but not every shape. This one covers it all!" Lang explains. "The algorithm is surprisingly complex, but that arises because it is comprehensive. It truly covers every possibility. And it is not just an abstract proof; it is readily computationally implementable."
The breakthrough could be seen as one of those computational achievements with no real practical outcome, but considering the influence of origami techniques across a broad array of recent innovations it isn't hard to see how this could be utilized in manufacturing and engineering. Bulletproof shields, robots, canoes, satellites and biobatteries are just a few examples to catch our eye in recent times. And with Demaine and Tachi planning to incorporate the algorithm into an updated version of Tachi's free Origamizer software that was originally released in 2008, the list is sure to grow.
Source: MIT