Kawasaki's theorem


Kawasaki's theorem is a theorem in the mathematics of paper folding that describes the crease patterns with a single vertex that may be folded to form a flat figure. It states that the pattern is flat-foldable if and only if alternatingly adding and subtracting the angles of consecutive folds around the vertex gives an alternating sum of zero.
Crease patterns with more than one vertex do not obey such a simple criterion, and are NP-hard to fold.
The theorem is named after one of its discoverers, Toshikazu Kawasaki. However, several others also contributed to its discovery, and it is sometimes called the Kawasaki–Justin theorem or Husimi's theorem after other contributors, Jacques Justin and Kôdi Husimi.

Statement

A one-vertex crease pattern consists of a set of rays or creases drawn on a flat sheet of paper, all emanating from the same point interior to the sheet. Each crease must be folded, but the pattern does not specify whether the folds should be mountain folds or valley folds. The goal is to determine whether it is possible to fold the paper so that every crease is folded, no folds occur elsewhere, and the whole folded sheet of paper lies flat.
To fold flat, the number of creases must be even. This follows, for instance, from Maekawa's theorem, which states that the number of mountain folds at a flat-folded vertex differs from the number of valley folds by exactly two folds. Therefore, suppose that a crease pattern consists of an even number of creases, and let be the consecutive angles between the creases around the vertex, in clockwise order, starting at any one of the angles. Then Kawasaki's theorem states that the crease pattern may be folded flat if and only if the alternating sum and difference of the angles adds to zero:
An equivalent way of stating the same condition is that, if the angles are partitioned into two alternating subsets, then the sum of the angles in either of the two subsets is exactly 180 degrees. However, this equivalent form applies only to a crease pattern on a flat piece of paper, whereas the alternating sum form of the condition remains valid for crease patterns on conical sheets of paper with nonzero defect at the vertex.

Local and global flat-foldability

Kawasaki's theorem, applied to each of the vertices of an arbitrary crease pattern, determines whether the crease pattern is locally flat-foldable, meaning that the part of the crease pattern near the vertex can be flat-folded. However, there exist crease patterns that are locally flat-foldable but that have no global flat folding that works for the whole crease pattern at once. conjectured that global flat-foldability could be tested by checking Kawasaki's theorem at each vertex of a crease pattern, and then also testing bipartiteness of an undirected graph associated with the crease pattern. However, this conjecture was disproven by, who showed that Hull's conditions are not sufficient. More strongly, Bern and Hayes showed that the problem of testing global flat-foldability is NP-complete.

Proof

To show that Kawasaki's condition necessarily holds for any flat-folded figure, it suffices to observe that, at each fold, the orientation of the paper is reversed. Thus, if the first crease in the flat-folded figure is placed in the plane parallel to the -axis, the next crease must be rotated from it by an angle of, the crease after that by an angle of , etc. In order for the paper to meet back up with itself at the final angle, Kawasaki's condition must be met.
Showing that the condition is also a sufficient condition is a matter of describing how to fold a given crease pattern so that it folds flat. That is, one must show how to choose whether to make mountain or valley folds, and in what order the flaps of paper should be arranged on top of each other. One way to do this is to choose a number such that the partial alternating sum
is as small as possible. Either and the partial sum is an empty sum that is also zero, or for some nonzero choice of the partial sum is negative. Then, accordion fold the pattern, starting with angle and alternating between mountain and valley folds, placing each angular wedge of the paper below the previous folds. At each step until the final fold, an accordion fold of this type will never self-intersect. The choice of ensures that the first wedge sticks out to the left of all the other folded pieces of paper, allowing the final wedge to connect back up to it.
An alternative proof of sufficiency can be used to show that there are many different flat foldings. Consider the smallest angle and the two creases on either side of it. Mountain-fold one of these two creases and valley-fold the other, choosing arbitrarily which fold to use for which crease. Then, glue the resulting flap of paper onto the remaining part of the crease pattern. The result of this gluing will be a crease pattern with two fewer creases, on a conical sheet of paper, that still satisfies Kawasaki's condition. Therefore, by mathematical induction, repeating this process will eventually lead to a flat folding. The base case of the induction is a cone with only two creases and two equal-angle wedges, which can obviously be flat-folded by using a mountain fold for both creases. There are two ways to choose which folds to use in each step of this method, and each step eliminates two creases. Therefore, any crease pattern with creases that satisfies Kawasaki's condition has at least different choices of mountain and valley folds that all lead to valid flat foldings.

History

In the late 1970s, Kôdi Husimi and David A. Huffman independently observed that flat-folded figures with four creases have opposite angles adding to, a special case of Kawasaki's theorem. Huffman included the result in a 1976 paper on curved creases, and
Husimi published the four-crease theorem in a book on origami geometry with his wife Mitsue Husimi.
The same result was published even earlier, in a pair of papers from 1966 by S. Murata that also included the six-crease case and the general case of Maekawa's theorem.
The fact that crease patterns with arbitrarily many creases necessarily have alternating sums of angles adding to was discovered by Kawasaki, by Stuart Robertson, and by Jacques Justin in the late 1970s and early 1980s.
Because of Justin's contribution to the problem, Kawasaki's theorem has also been called the Kawasaki–Justin theorem.
The fact that this condition is sufficient—that is, that crease patterns with evenly many angles, alternatingly summing to can always be flat-folded—may have been first stated by.
Kawasaki himself has called the result Husimi's theorem, after Kôdi Husimi, and some other authors have followed this terminology as well. The name "Kawasaki's theorem" was first given to this result in Origami for the Connoisseur by Kunihiko Kasahara and Toshie Takahama.
credits the lower bound of on the number of different flat-foldings of a crease pattern meeting the conditions of the theorem to independent work in the early 1990s by Azuma, Justin, and Ewins and Hull.
Although Kawasaki's theorem completely describes the folding patterns that have flat-folded states, it does not describe the folding process needed to reach that state. For some folding patterns, it may be necessary to curve or bend the paper while transforming it from a flat sheet to its flat-folded state, rather than keeping the rest of the paper flat and only changing the dihedral angles at each fold. For rigid origami, additional conditions are needed on a folding pattern to allow it to move from an unfolded state to a flat-folded state.