Origami is NP-complete 

E.A. Elsayed gave a talk about reliability at UW-Madison last week. The most interesting topic he talked about was the mathematics of folding flat paper into intricate designs (origami!). Determining whether a series of creases can be flattened is NP-complete through a reduction from the Not-All-Equal 3-SAT*

There are some basic mathematical principles that describe whether folding is possible. For example, the angles formed at a corner must sum to 360 degrees or it cannot be flattened. For example, the pyramids of Egypt cannot be flattened.

There are four mathematical rules for producing flat-foldable origami crease patterns:[7]

  1. The regions between the creases can be colored with two colors, differing across each crease. Equivalently every vertex has an even number of creases.
  2. Maekawa’s theorem: at any vertex the number of valley and mountain folds always differ by two in either direction.
  3. Kawasaki’s theorem: at any vertex, the sum of all the odd angles adds up to 180 degrees, as do the even.
  4. A sheet can never penetrate a fold.

(Thanks Wikipedia!)

 

Honeycomb pattern folded from a sheet of thick craft paper. The pattern can be compressed and expanded like an accordion.

Chevron pattern folded from a sheet of aluminum

 

E.A. Elsayed talks about how to manufacture folded designs.

Make your own chevrom here:

* Bern, M. and Hayes, B., “The complexity of flat origami”, Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, (1996) 175–183.

* Thomas C. Hull (2002). “The Combinatorics of Flat Folds: a Survey” (PDF). The Proceedings of the Third International Meeting of Origami Science, Mathematics, and Education. AK Peters. ISBN 978-1-56881-181-9.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: