# Algorithm generates origami folding patterns for any shape

June 23, 2017In a 1999 paper, Erik Demaine -- now an MIT professor of electrical engineering and computer science, but then an 18-year-old PhD student at the University of Waterloo, in Canada -- described an algorithm that could determine how to fold a piece of paper into any conceivable 3-D shape.

It was a milestone paper in the field of computational origami, but the algorithm didn't yield very practical folding patterns. Essentially, it took a very long strip of paper and wound it into the desired shape. The resulting structures tended to have lots of seams where the strip doubled back on itself, so they weren't very sturdy.

At the Symposium on Computational Geometry in July, Demaine and Tomohiro Tachi of the University of Tokyo will announce the completion of a quest that began with that 1999 paper: a universal algorithm for folding origami shapes that guarantees a minimum number of seams.

"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. "It's 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. The new result promises to be much more efficient. It's a totally different strategy for thinking about how to make a polyhedron."

Demaine and Tachi are also working to implement the algorithm in a new version of Origamizer, the free software for generating origami crease patterns whose first version Tachi released in 2008.

**Maintaining boundaries**

The researchers' algorithm designs crease patterns for producing any polyhedron -- that is, a 3-D surface made up of many flat facets. Computer graphics software, for instance, models 3-D objects as polyhedra consisting of many tiny triangles. "Any curved shape you could approximate with lots of little flat sides," Demaine explains.

Technically speaking, the guarantee that the folding will involve the minimum number of seams means that it preserves the "boundaries" of the original piece of paper. Suppose, for instance, that you have a circular piece of paper and want to fold it into a cup. Leaving a smaller circle at the center of the piece of paper flat, you could bunch the sides together in a pleated pattern; in fact, some water-cooler cups are manufactured on this exact design.

In this case, the boundary of the cup -- its rim -- is the same as that of the unfolded circle -- its outer edge. The same would not be true with the folding produced by Demaine and his colleagues' earlier algorithm. There, the cup would consist of a thin strip of paper wrapped round and round in a coil -- and it probably wouldn't hold water.

"The new algorithm is supposed to give you much better, more practical foldings," Demaine says. "We don't know how to quantify that mathematically, exactly, other than it seems to work much better in practice. But we do have one mathematical property that nicely distinguishes the two methods. The new method keeps the boundary of the original piece of paper on the boundary of the surface you're trying to make. We call this watertightness."

A closed surface -- such as a sphere -- doesn't have a boundary, so an origami approximation of it will require a seam where boundaries meet. But "the user gets to choose where to put that boundary," Demaine says. "You can't get an entire closed surface to be watertight, because the boundary has to be somewhere, but you get to choose where that is."

**Lighting fires**

The algorithm begins by mapping the facets of the target polyhedron onto a flat surface. But whereas the facets will be touching when the folding is complete, they can be quite far apart from each other on the flat surface. "You fold away all the extra material and bring together the faces of the polyhedron," Demaine says.

Folding away the extra material can be a very complex process. Folds that draw together multiple faces could involve dozens or even hundreds of separate creases.

Developing a method for automatically calculating those crease patterns involved a number of different insights, but a central one was that they could be approximated by something called a Voronoi diagram. To understand this concept, imagine a grassy plain. A number of fires are set on it simultaneously, and they all spread in all directions at the same rate. The Voronoi diagram -- named after the 19th-century Ukrainian mathematician Gyorgy Voronoi -- describes both the location at which the fires are set and the boundaries at which adjacent fires meet. In Demaine and Tachi's algorithm, the boundaries of a Voronoi diagram define the creases in the paper.

"We have to tweak it a little bit in our setting," Demaine says. "We also imagine simultaneously lighting a fire on the entire polygon of the polyhedron and growing out from there. But that concept was really useful. The challenge is to set up where to light the fires, essentially, so that the Voronoi diagram has all the properties we need."

-end-

**Additional background**

Paper: "Origamizer: A Practical Algorithm for Folding Any Polyhedron http://erikdemaine.org/papers/Origamizer_SoCG2017/paper.pdf

ARCHIVE: "Super Mario Brothers" is hard http://news.mit.edu/2016/mario-brothers-hard-complexity-class-pspace-0601

ARCHIVE: Origami robot folds itself up, crawls away http://news.mit.edu/2014/mobile-folding-robots-0807

ARCHIVE: Bake your own robot http://news.mit.edu/2014/bake-your-own-robot-0530

ARCHIVE: The math of the Rubik's cube http://news.mit.edu/2011/rubiks-cube-0629

Massachusetts Institute of Technology

**Related Algorithm Articles:**

Scientists use algorithm to peer through opaque brains

A new algorithm helps scientists record the activity of individual neurons within a volume of brain tissue.

A new algorithm helps scientists record the activity of individual neurons within a volume of brain tissue.

Algorithm generates origami folding patterns for any shape

A new algorithm generates practical paper-folding patterns to produce any 3-D structure.

A new algorithm generates practical paper-folding patterns to produce any 3-D structure.

New algorithm tracks neurons in bendy brain of freely crawling worm

Scientists at Princeton University have developed a new algorithm to track neurons in the brain of the worm Caenorhabditis elegans while it crawls.

Scientists at Princeton University have developed a new algorithm to track neurons in the brain of the worm Caenorhabditis elegans while it crawls.

Does my algorithm work? There's no shortcut for community detection

Community detection is an important tool for scientists studying networks, but a new paper published in Science Advances calls into question the common practice of using metadata for ground truth validation.

Community detection is an important tool for scientists studying networks, but a new paper published in Science Advances calls into question the common practice of using metadata for ground truth validation.

'Cyclops' algorithm spots daily rhythms in cells

Humans, like virtually all other complex organisms on Earth, have adapted to their planet's 24-hour cycle of sunlight and darkness.

Humans, like virtually all other complex organisms on Earth, have adapted to their planet's 24-hour cycle of sunlight and darkness.

An algorithm that knows when you'll get bored with your favorite mobile game

Researchers from the Tokyo-based company Silicon Studio, led by Spanish data scientist África Periáñez, have developed a new algorithm that predicts when a user will leave a mobile game.

Researchers from the Tokyo-based company Silicon Studio, led by Spanish data scientist África Periáñez, have developed a new algorithm that predicts when a user will leave a mobile game.

Algorithm identified Trump as 'not-married'

Scientists from Russia and Singapore created an algorithm that predicts user marital status with 86% precision using data from three social networks instead of one.

Scientists from Russia and Singapore created an algorithm that predicts user marital status with 86% precision using data from three social networks instead of one.

A novel positioning algorithm based on self-adaptive algorithm

Much attention has been paid to the Taylor series expansion (TSE) method these years, which has been extensively used for solving nonlinear equations for its good robustness and accuracy of positioning.

Much attention has been paid to the Taylor series expansion (TSE) method these years, which has been extensively used for solving nonlinear equations for its good robustness and accuracy of positioning.

Algorithm can create a bridge between Clinton and Trump supporters

The article that received the best student-paper award in the Tenth International Conference on Web Search and Data Mining (WSDM 2017) builds algorithmic techniques to mitigate the rising polarization by connecting people with opposing views -- and evaluates them on Twitter.

The article that received the best student-paper award in the Tenth International Conference on Web Search and Data Mining (WSDM 2017) builds algorithmic techniques to mitigate the rising polarization by connecting people with opposing views -- and evaluates them on Twitter.

Deep learning algorithm does as well as dermatologists in identifying skin cancer

In hopes of creating better access to medical care, Stanford researchers have trained an algorithm to diagnose skin cancer.

In hopes of creating better access to medical care, Stanford researchers have trained an algorithm to diagnose skin cancer.

**Related Algorithm Reading:**

## Best Science Podcasts 2019

We have hand picked the**best science podcasts**for 2019. Sit back and enjoy new science podcasts updated daily from your favorite science news services and scientists.

**Now Playing: TED Radio Hour**

**Climate Crisis**

There's no greater threat to humanity than climate change. What can we do to stop the worst consequences? This hour, TED speakers explore how we can save our planet and whether we can do it in time. Guests include climate activist Greta Thunberg, chemical engineer Jennifer Wilcox, research scientist Sean Davis, food innovator Bruce Friedrich, and psychologist Per Espen Stoknes.

**Now Playing: Science for the People**

**#527 Honey I CRISPR'd the Kids**

This week we're coming to you from Awesome Con in Washington, D.C. There, host Bethany Brookshire led a panel of three amazing guests to talk about the promise and perils of CRISPR, and what happens now that CRISPR babies have (maybe?) been born. Featuring science writer Tina Saey, molecular biologist Anne Simon, and bioethicist Alan Regenberg. A Nobel Prize winner argues banning CRISPR babies won’t work Geneticists push for a 5-year global ban on gene-edited babies A CRISPR spin-off causes unintended typos in DNA News of the first gene-edited babies ignited a firestorm The researcher who created CRISPR twins defends...