## Wednesday, March 10, 2004

### Computational Origami OR How to eat sugary cereal that's good for you

Computational geometry draws its parentage both from geometry, and from the theory of computation. As such, it has both formal aspects (only professional mathematicians need apply!) and some gloriously innovative and entertaining dimensions that give it wide reach beyond the academic environment. Heck, you might be doing computational geometry without even knowing it !

Origami (and folding) is one such area. The field of computational origami sprung up in an attempt to analyze folding patterns and ask questions like: 'Here's a set of creases in a sheet of paper: how do I get there from a blank sheet ?'

Not unlike Euclid's axioms, there are basic axioms underpinning the science of folding. These were developed by mathematician Humiaki Huzita in 1992.

Robert Lang, credited with being one of the pioneers of the field of computational origami, has a program called TreeMaker that you can use to design origami designs from scratch.

Alas, the question we asked earlier has an answer, but like most questions in theoretical computer scieince, it is an answer we may not like: Determining whether a given sequence of creases can be achieved by flat folding is NP-hard. This is due to Marshall Bern and Barry Hayes.

You might wonder, "All this is fine and dandy, but can I get a job doing computational origami ?". As it turns out...
Erik Demaine, a professor at MIT, is known (among other things) for his work on folding and origami. He has a very nice folding page.

David Eppstein, whose geometry pages merit many entries of their own, has another nice page on folding.

... Of course, with great power comes great responsibility. Not all origamists use their superpowers for good....

UPDATE: Looks like I'm not the first to comment on computational origami