Kawasaki's theorem
Encyclopedia
Kawasaki's theorem is a theorem
in the mathematics of paper folding
, named after Toshikazu Kawasaki
, that gives a criterion for determining whether a crease pattern
with a single vertex
may be folded to form a flat figure.
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.
of an undirected graph associated with the crease pattern, but this conjecture was disproven by , who showed that the problem of testing global flat-foldability is NP-complete
.
Showing that the condition is also a sufficient condition is a matter of describing how to fold a given crease pattern (that is, 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) so that it folds flat. 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, and 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 is to consider the smallest angle and the two creases on either side of it. If one of these two creases is mountain-folded and the other valley-folded, and then the resulting flap of paper is glued down onto the remaining part of the crease pattern, the result 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. Using this method, it can be shown that any crease pattern that satisfies Kawasaki's condition has at least different choices of mountain and valley folds that all lead to valid flat foldings.
independently discovered the special case of Kawasaki's theorem for crease patterns with four creases; Huffman called it the "critical
condition". The theorem for crease patterns with arbitrarily many creases was discovered by Kawasaki, by Stuart Robertson, and by Jacques Justin (again, independently of each other) in the late 1970s and early 1980s. Because of Justin's contribution to the problem, it has also been called the Kawasaki–Justin theorem.
Kawasaki himself has called the result Husimi's theorem, after Yasuji 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 (Japan Publications, 1987).
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.
Theorem
In mathematics, a theorem is a statement that has been proven on the basis of previously established statements, such as other theorems, and previously accepted statements, such as axioms...
in the mathematics of paper folding
Mathematics of paper folding
The art of origami or paper folding has received a considerable amount of mathematical study. Fields of interest include a given paper model's flat-foldability and the use of paper folds to solve mathematical equations.-Flat folding:The construction of origami models is sometimes shown as crease...
, named after Toshikazu Kawasaki
Toshikazu Kawasaki
is a Japanese paperfolder and origami theorist who is known for his geometrically innovative models. He is particularly famous for his series of fourfold symmetry "roses", all based on a twisting maneuver that allows the petals to seem to curl out from the center of the flower...
, that gives a criterion for determining whether a crease pattern
Crease pattern
A Crease Pattern is an origami diagram type that consists of all or most of the creases in the final model, rendered into one image. This comes in handy for diagramming complex and super-complex models, where the model is often not simple enough to diagram efficiently.The use of crease patterns...
with a single vertex
Vertex (geometry)
In geometry, a vertex is a special kind of point that describes the corners or intersections of geometric shapes.-Of an angle:...
may be folded to form a flat figure.
Statement of the theorem
Maekawa's theorem states that the number of mountain folds in a flat-folded vertex figure differs from the number of valley folds by exactly two folds. From this it follows that the total number of folds must be even. Therefore, suppose that a crease pattern consists of an even number of creases radiating from a single vertex , without specification of which creases should be mountain folds and which should be valley folds. In this crease pattern, let be the consecutive angles between the creases around , in clockwise order, starting at any one of the angles. Then Kawasaki's theorem is the statement 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
Defect (geometry)
In geometry, the defect means the failure of some angles to add up to the expected amount of 360° or 180°, when such angles in the plane would...
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 bipartitenessBipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
of an undirected graph associated with the crease pattern, but this conjecture was disproven by , who showed that the problem of testing global flat-foldability is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
.
Proof
To show that Kawaski'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 (because the second angle has the reverse orientation from the first), 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 (that is, 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) so that it folds flat. 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
Empty sum
In mathematics, an empty sum, or nullary sum, is a summation involving no terms at all. The value of any empty sum of numbers is conventionally taken to be zero...
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, and 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 is to consider the smallest angle and the two creases on either side of it. If one of these two creases is mountain-folded and the other valley-folded, and then the resulting flap of paper is glued down onto the remaining part of the crease pattern, the result 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
Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
, 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. Using this method, it can be shown that any crease pattern 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, Yasuji Husimi and David A. HuffmanDavid A. Huffman
David Albert Huffman was a pioneer in computer science. He is well-known for his Huffman coding. David Huffman died at the age of 74 after a 10-month battle with cancer.-Education:...
independently discovered the special case of Kawasaki's theorem for crease patterns with four creases; Huffman called it the "critical
Pi
' is a mathematical constant that is the ratio of any circle's circumference to its diameter. is approximately equal to 3.14. Many formulae in mathematics, science, and engineering involve , which makes it one of the most important mathematical constants...
condition". The theorem for crease patterns with arbitrarily many creases was discovered by Kawasaki, by Stuart Robertson, and by Jacques Justin (again, independently of each other) in the late 1970s and early 1980s. Because of Justin's contribution to the problem, it has also been called the Kawasaki–Justin theorem.
Kawasaki himself has called the result Husimi's theorem, after Yasuji 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
Kunihiko Kasahara
is a Japanese origami master. He has made hundreds of models, from simple lion masks to complex modular origami, such as a small stellated dodecahedron. He does not specialize in what is known as "super complex origami", but rather he likes making simple, elegant animals, and modular designs such...
and Toshie Takahama (Japan Publications, 1987).
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.