Kawasaki's theorem

In this example, the alternating sum of angles (starting from the triangle in the bottom of the crease pattern) is 90 − 45 + 22.5 − 22.5 + 45 − 90 + 22.5 − 22.5 = 0. Since it adds to zero, the crease pattern may be flat-folded, as shown.

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.

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.[1] Therefore, suppose that a crease pattern consists of an even number 2n of creases radiating from a single vertex v, without specification of which creases should be mountain folds and which should be valley folds. In this crease pattern, let α1, α2, ⋯, α2n be the consecutive angles between the creases around v, 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:

α1 − α2 + α3 − ⋯ + α2n − 1 − α2n = 0

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.[2] 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.[3]

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.[1] Tom Hull (1994) 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,[4] but this conjecture was disproven by Bern & Hayes (1996), who showed that the problem of testing global flat-foldability is NP-complete.[5]

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 x-axis, the next crease must be rotated from it by an angle of α1, the crease after that by an angle of α1 − α2 (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.[1][2][6][7]

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 i such that the partial alternating sum

α1 − α2 + α3 − ⋯ + α2i − 1 − α2i

is as small as possible: either i = 0 and the partial sum is an empty sum that is also zero, or for some nonzero choice of i the partial sum is negative. Then, accordion fold the pattern, starting with angle α2i + 1 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 i 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.[7]

An alternative proof of sufficiency is to consider the smallest angle αi 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 2n different choices of mountain and valley folds that all lead to valid flat foldings.[8]

History

In the late 1970s, Yasuji Husimi and David A. Huffman independently discovered the special case of Kawasaki's theorem for crease patterns with four creases; Huffman called it the "critical π condition".[9][10] 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.[5][9][11][12][13][14] Because of Justin's contribution to the problem, it has also been called the Kawasaki–Justin theorem.[15]

Kawasaki himself has called the result Husimi's theorem, after Yasuji Husimi, and some other authors have followed this terminology as well.[6][16] 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).[1]

Hull (2003) credits the lower bound of 2n 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,[17] Justin,[13] and Ewins and Hull.

References

  1. 1 2 3 4 Hull, Tom, MA 323A Combinatorial Geometry!: Notes on Flat Folding, retrieved 2011-04-12.
  2. 1 2 Alsina, Claudi; Nelsen, Roger (2010), Charming Proofs: A Journey Into Elegant Mathematics, Dolciani Mathematical Expositions, 42, Mathematical Association of America, p. 57, ISBN 978-0-88385-348-1.
  3. ↑ Hull, Tom (2002), "The combinatorics of flat folds: a survey", Origami3: Third International Meeting of Origami Science, Mathematics, and Education, AK Peters, pp. 29–38, ISBN 978-1-56881-181-9.
  4. ↑ Hull, Tom (1994), "On the mathematics of flat origamis" (PDF), Congressus Numerantium, 100: 215–224.
  5. 1 2 Bern, Marshall; Hayes, Barry (1996), "The complexity of flat origami", Proc. 7th ACM-SIAM Symposium on Discrete algorithms (SODA '96), pp. 175–183.
  6. 1 2 Kawasaki, Toshikazu (2005), Roses, Origami & Math, Japan Publications Trading, p. 139, ISBN 978-4-88996-184-3.
  7. 1 2 Demaine, Erik (Fall 2010), "Sept. 15: Single-vertex crease patterns", Course Notes for 6.849: Geometric Folding Algorithms: Linkages, Origami, Polyhedra, Massachusetts Institute of Technology, retrieved 2011-04-13.
  8. ↑ Hull, Thomas (2003), "Counting mountain-valley assignments for flat folds" (PDF), Ars Combinatoria, 67: 175–187, MR 1973236.
  9. 1 2 Hull, Tom (Fall 2010), "Maekawa and Kawasaki's Theorems Revisited and Extended", Guest lecture, 6.849, Massachusetts Institute of Technology.
  10. ↑ Wertheim, Margaret (June 22, 2004), "Cones, Curves, Shells, Towers: He Made Paper Jump to Life", New York Times.
  11. ↑ Robertson, S. A. (1977), "Isometric folding of Riemannian manifolds", Proceedings of the Royal Society of Edinburgh. Section A. Mathematics, 79 (3-4): 275–284, MR 0487893.
  12. ↑ Justin, J. (June 1986), British Origami: 30 Missing or empty |title= (help). As cited by Hull's MA 323A notes.
  13. 1 2 Justin, J. (1994), "Towards a mathematical theory of origami", 2nd Int. Meeting of Origami Science, Otsu, Japan. As cited by Bern & Hayes (1996).
  14. ↑ Kawasaki, T. (1989), "On the relation between mountain-creases and valley-creases of a flat origami", in Huzita, H., Origami Science and Technology, pp. 229–237. As cited by Bern & Hayes (1996).
  15. ↑ O'Rourke, Joseph (2011), "4.5 The Kawasaki–Justin theorem", How To Fold It: The Mathematics of Linkages, Origami, and Polyhedra, Cambridge University Press, pp. 66–68.
  16. ↑ Kaino, K. (2007), "Four-dimensional geometry and folding regular tetrahedron", in Fujita, Shigeji; Obata, Tsunehiro; Suzuki, Akira, Statistical and condensed matter physics: over the horizon, Nova Publishers, pp. 101–112 [102], ISBN 978-1-60021-758-6.
  17. ↑ Azuma, H. (1994), "Some mathematical observation on flat foldings", 2nd Int. Meeting of Origami Science, Otsu, Japan. As cited by Hull (2003)

External links

This article is issued from Wikipedia - version of the 10/4/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.