Kawasaki's theorem

This is a good article. Click here for more information.
Source: Wikipedia, the free encyclopedia.

In this example, the alternating sum of angles (clockwise from the bottom) 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.

Kawasaki's theorem or Kawasaki–Justin 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.[1]

Statement

A one-vertex

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

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.[3] Therefore, suppose that a crease pattern consists of an even number 2n of creases, and let α1, α2, ⋯, α2n 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:

α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.

defect at the vertex.[2]

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

NP-complete.[6]

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

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 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. 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.[5]

An alternative proof of sufficiency can be used to show that there are many different flat foldings. Consider the smallest angle αi 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 2n creases that satisfies Kawasaki's condition has at least 2n different choices of mountain and valley folds that all lead to valid flat foldings.[9]

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.[10][11] Huffman included the result in a 1976 paper on curved creases,[12] and Husimi published the four-crease theorem in a book on origami geometry with his wife Mitsue Husimi.[13] 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.[14]

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 (again, independently of each other) in the late 1970s and early 1980s.[6][10][15][16][17][18] Because of Justin's contribution to the problem, Kawasaki's theorem has also been called the Kawasaki–Justin theorem.[19] 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 Hull (1994).[5]

Kawasaki himself has called the result Husimi's theorem, after Kôdi Husimi, and some other authors have followed this terminology as well.[7][20] 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).[3]

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,[21] Justin,[17] and Ewins and Hull.[9]

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 (multi-vertex) folding patterns, it is 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 (a type of folding that keeps the surface flat except at its folds, suitable for hinged panels of rigid material rather than flexible paper), the condition of Kawasaki's theorem turns out to be sufficient for a single-vertex crease pattern to move from an unfolded state to a flat-folded state.[22]

References

  1. ^ The name "Yasuji Husimi" appearing in Kawasaki (2005) and sometimes associated with this theorem is a misreading of the kanji "康治" in Kôdi Husimi's name.
  2. ^
    ISBN 978-1-56881-181-9
    .
  3. ^ a b c d Hull, Tom, MA 323A Combinatorial Geometry!: Notes on Flat Folding, retrieved 2011-04-12.
  4. ^
    ISBN 978-0-88385-348-1
    .
  5. ^ a b c Hull, Tom (1994), "On the mathematics of flat origamis" (PDF), Congressus Numerantium, 100: 215–224.
  6. ^
    ISBN 9780898713664
    .
  7. ^
    ISBN 978-4-88996-184-3
    .
  8. ^ 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.
  9. ^
    MR 1973236
    .
  10. ^ a b Hull, Tom (Fall 2010), "Maekawa and Kawasaki's Theorems Revisited and Extended", Guest lecture, 6.849, Massachusetts Institute of Technology.
  11. New York Times
    .
  12. S2CID 17965418
    .
  13. ^ Husimi, K.; Husimi, M. (1979), The Geometry of Origami (in Japanese), Tokyo: Nihon Hyouronsha. 2nd ed., 1984,
    ISBN 978-4535781399
    .
  14. ^ Murata, S. (1966), "The theory of paper sculpture, I", Bulletin of Junior College of Art (in Japanese), 4: 61–66; Murata, S. (1966), "The theory of paper sculpture, II", Bulletin of Junior College of Art (in Japanese), 5: 29–37.
  15. S2CID 122398261
    .
  16. ^ Justin, J. (June 1986), "Mathematics of origami, part 9", British Origami: 30. As cited by Hull's MA 323A notes.
  17. ^ a b Justin, J. (1994), "Towards a mathematical theory of origami", 2nd Int. Meeting of Origami Science, Otsu, Japan{{citation}}: CS1 maint: location missing publisher (link). As cited by Bern & Hayes (1996).
  18. ^ Kawasaki, T. (1989), "On the relation between mountain-creases and valley-creases of a flat origami", in Huzita, H. (ed.), Origami Science and Technology, pp. 229–237. As cited by Bern & Hayes (1996).
  19. ^ 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.
  20. ISBN 978-1-60021-758-6
    .
  21. ^ Azuma, H. (1994), "Some mathematical observation on flat foldings", 2nd Int. Meeting of Origami Science, Otsu, Japan{{citation}}: CS1 maint: location missing publisher (link). As cited by Hull (2003)
  22. S2CID 7181079
    .

External links
Retrieved from "https://en.wikipedia.org/w/index.php?title=Kawasaki%27s_theorem&oldid=1182983816"