# Fold-and-cut problem in three dimensions

The fold-and-cut theory states that "Any shape with straight sides can be cut from a single (idealized) sheet of paper by folding it flat and making a single straight complete cut. Such shapes include polygons"

My question

Question 1 What is the time complexity for finding such a crease pattern?
Question 2 How do we express; $\chi(P)$ ie the minimum number of folds required to make a crease pattern from which the polygon $P$ can be cut out?
Question 3 Does the fold-and-cut-theorem have a three dimensional analog?

Would also request for a reference to the proof.

• Q3: One can state a higher-dimensional analog, but no one has proven any result in three or higher dimensions. – Joseph O'Rourke Sep 24 '13 at 16:17
• Thanks. Do you also have any info on the algorithm for finding the crease pattern ( or is it talked about in the proof itself). – ARi Sep 24 '13 at 16:39

(Revised) Let me first answer your request for a reference, and then reply to the three questions. The most detailed proof of the One-Cut Theorem is in Chapter 17 of

Here is a challenging 2D example to fold from that chapter (red=mountain, green=valley):

(This one works best with a papercutter!) Here is a link to this and other templates, suitable for classroom use.

Q3. (From my comment:) One can state a higher-dimensional analog, but no one has proven any result in three or higher dimensions.

Q1 & Q2. These two questions (algorithmic complexity, combinatorial complexity) are two sides of the same issue. Essentially, neither complexity question has been answered precisely. However, in some sense the answers are known. The best source is the first paper on the topic, which precedes the book reference above by a decade (and much was learned in that decade):

Bern, M., Demaine, E., Eppstein, D., & Hayes, B. "A disk-packing algorithm for an origami magic trick." International Conference on Fun with Algorithms. June. 1998. (Citeseer PDF download)

Here is their paragraph on complexity (the algorithm is based on disk-packing):

For local feature size, see the Wikipedia article. I doubt there could be a complexity bound in terms of $n$, the number of line segments in the drawing to be folded and cut; rather, it must depend on the geometry, as does the local feature size.

• id like to do the turtle, but inept as i am, im finding it hard without an order of folds or a video to help me. If there is a thing like that, id really appreciate a link :) – user80715 Sep 25 '15 at 19:09
• Sorry, I don't have a video. Work on the left half first, the feet, the back, and handle the neck (the most complex part) last. There is not just one way to fold it---the tucking over and under can vary. – Joseph O'Rourke Sep 25 '15 at 19:52

In response to @redhound. Now updated with step-by-step instructions online:

The turtle nearly fully folded. The black lines all align.

The hole remaining after 1-cut.