MIT Research News' Journal

Origami anything

In 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.”

Completed quest

“It’s very impressive stuff,” says Robert Lang, one of the pioneers of computational origami and a fellow of the American Mathematical Society, who in 2001 abandoned a successful career in optical engineering to become a full-time origamist. “It completes what I would characterize as a quest that began some 20-plus years ago: a computational method for efficiently folding any specified shape from a sheet of paper. 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! 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.”

Joseph O’Rourke, a professor of mathematics and computer science at Smith College and the author of How To Fold It: The Mathematics of Linkages, Origami, and Polyhedra, agrees. “What was known before was either ‘cheating’ — winding the polyhedron with a thin strip — or not guaranteed to succeed,” he says. “Their new algorithm is guaranteed to produce a folding, and it is the opposite of cheating in that every facet of the polyhedron is covered by a ‘seamless’ facet of the paper, and the boundary of the paper maps to the boundary of the polyhedral manifold — their ‘watertight’ property. Finally, the extra structural ‘flash’ needed to achieve their folding can all be hidden on the inside and so is invisible.”

Illuminating the developing world’s “invisible” consumers

While on location in remote areas of Kenya, researching automation and home manufacturing for his doctoral dissertation, Kenfield Griffith PhD ’12 encountered a significant lack of data.

For example, information he needed about whether people had access to indoor plumbing was scarce or nonexistent — and conducting traditional surveys to gather the data would be arduous and time consuming. But nearly all rural Kenyans, he realized, had texting-capable cell phones.

Back in his MIT dorm room, Griffith built a platform that allowed users to easily create and send text message-based surveys, and monitor incoming results in real time on a web dashboard. Returning to Kenya, he amassed hundreds of participants to use the platform, and completed his research.

“I was getting interesting information that you couldn’t find anywhere else, from people who didn’t have a bathroom but had mobile phones,” Griffith says. “That was the epiphany for me, where I said, ‘This could be an opportunity to really understand consumers on the ground and create conversations at scale.’”

In 2012, Griffith commercialized the platform as mSurvey, which is now being used by companies to gain insights into the purchasing behavior of people living in previously hard-to-reach communities in Kenya, the Philippines, Jamaica, Trinidad and Tobago, and other locations in Africa and the Caribbean. In return for their feedback, participants receive mobile money.

Researchers are also using the platform for tracking and improving HIV medication adherence across Africa, monitoring pregnancy and abortion results of Kenyan women, and other studies. The City of San Francisco has started using the platform to improve services for people living with HIV and AIDS.

In March, mSurvey partnered with Kenya’s leading mobile provider, Safaricom, to launch Consumer Wallet, a platform that, for the first time, tracks consumer cash spending in Kenya. “Consumers in the most rural areas of Kenya, and other emerging markets, don’t really have a voice,” says Griffith, who studied design and computation in the Department of Architecture at MIT and is now CEO of mSurvey. “We’re capturing that invisible consumer.”

Instrumental in his startup’s success, Griffith says, was the funding he received from the Legatum Center for Development and Entrepreneurship, which offers resources to MIT students, faculty, and departments that are looking to improve the lives of people in the developing world. The center now lists mSurvey as a successful case study.

Conversations at scale

With mSurvey, users sign onto a web dashboard to create a survey conversation of multiple-choice and open-ended questions. They set the number of participants, and an algorithm randomly shoots off the surveys to the selected number from the “universe” of participants; in Kenya, that’s 21 million, or nearly half the population. To narrow down this list, users can also set parameters, such as age, gender, and location. By partnering with mobile-money providers, mSurvey sends small amounts of mobile money to all participants for completing all questions.

Companies might use the surveys to brand products. If a survey indicates that most people eat, say, yogurt because it tastes sweet and is healthy, the company may emphasize those descriptors in advertisement campaigns.

But an important perk of mSurvey is collecting data in real-time. Companies can view how advertisement campaigns are doing and potentially revise the campaign on the fly. Restaurants, banks, and coffee houses use mSurvey to get quick customer feedback and refine their offerings and services. Executives have been known to gather data on how a product is doing within hours before walking into board meeting, Griffith says.

“The platform gives companies the ability to have these conversations with customers in real time, at scale,” Griffith says.

As an entrepreneur himself, Griffith notes that the platform could also help fledgling entrepreneurs in Kenya and other emerging markets find out if locals can afford their products and services. “With entrepreneurs, time is of the essence. We don’t have three months to go through this elaborate surveying process. We want that information about the consumer now,” he says.

With Consumer Wallet, Griffith says, companies can now gain insight into Kenyan cash purchases to make better decisions about what products and services the people need and want. About 55 percent of Africa’s economy comprises cash purchases, he says. In the past, companies and researchers have tracked purchases by having people in developing countries keep records in journals.

“We’ve digitized that process,” Griffith says. “We’re talking to thousands of consumers to understand their spending habits day after day.”

The startup is now looking to expand Consumer Wallet across Africa. Collecting cash-spending data across the continent could lead to greater investments, Griffith says. By 2020, he says, consumer spending in Africa will be about $1.2 trillion, but investors need to know where that money goes.

“You don’t invest is something you don’t know,” Griffith says. “We’re proud, because we can create this visibility into this cash economy that wasn’t formalized before. Now we’ve formalized it using a mobile phone.”

Impact on health

What began as part of a doctoral dissertation has also returned to academia, for the benefit of public health. Researchers are using mSurvey to better connect with communities in Africa and here in the U.S. To conduct surveys, researchers generally recruit clinicians to conduct traditional surveys in the country of interest, which is time-consuming and can result in lack of data or incorrect analyses. On the other hand, mSurvey is quick, accurate, and well-regarded among participants.

Among notable mSurvey case study participants is Harvard Medical School, which has been using mSurvey for three years to monitor and improve adherence to an HIV-suppressing drug, called pre-exposure prophylaxis (PrEP), among “discordant” couples in Kenya and Uganda. Over nine months, the researchers enrolled nearly 400 HIV-negative partners who had HIV-positive partners, to receive daily surveys asking about their adherence and sexual behavior, with aims of quantifying their risk. A vast majority of participants reacted positively to mSurvey, and the researchers used the results to develop effective text-based intervention techniques to boost adherence.

A similar study — measuring PrEP and other medication adherence among discordant couples to ensure safer pregnancies — was conducted by the Washington University at Seattle, also with useful results.

In its effort to eliminate all new HIV infections by 2020, the San Francisco Department of Public Health is using mSurvey to help people living with HIV better engage with service programs. Clients receive daily surveys asking about their mental health, substance use, and support systems. They also have access to real-time, personalized support.

At the end of the day, Griffith says the platform’s value lies in its potential for scalable impact, whether for commercial or research purposes. “That impact could be quantified by more customers using a product. In the research sense, the medication is a product too. You want more people to have access to this medication,” he says. “Everyone wants to have impact.”