Big-little-big lemma

Last updated

In the mathematics of paper folding, the big-little-big lemma is a necessary condition for a crease pattern with specified mountain folds and valley folds to be able to be folded flat. [1] It differs from Kawasaki's theorem, which characterizes the flat-foldable crease patterns in which a mountain-valley assignment has not yet been made. Together with Maekawa's theorem on the total number of folds of each type, the big-little-big lemma is one of the two main conditions used to characterize the flat-foldability of mountain-valley assignments for crease patterns that meet the conditions of Kawasaki's theorem. [2] Mathematical origami expert Tom Hull calls the big-little-big lemma "one of the most basic rules" for flat foldability of crease patterns. [1]

Contents

Statement

The lemma concerns the angles made by consecutive pairs of creases at a single vertex of the crease pattern. It states that if any one of these angles is a local minimum (that is, smaller than the two angles on either side of it), then exactly one of the two creases bounding the angle must be a mountain fold and exactly one must be a valley fold. [1] [2]

Generalization and applications

A generalized version of the lemma holds for a sequence of equal angles at a single vertex, surrounded on both sides by a larger angle. For such a sequence, the number of mountain and valley folds bounding any of these angles must either be equal, or differ by one. [3] It can be used as part of a linear time algorithm that tests whether a folding pattern with a single vertex can be folded flat, by repeatedly looking for sequences of angles that obey the lemma and pinching them off, until either getting stuck or reducing the input to two equal angles bounded by two creases of the same type as each other. [4] [5]

History

In their book Geometric Folding Algorithms , Erik Demaine and Joe O'Rourke credit the lemma to publications of Toshikazu Kawasaki in 1989, and Jacques Justin in 1994. [2] [6] [7]

Related Research Articles

<i>Origami</i> Traditional Japanese art of paper folding

Origami is the art of paper folding, which is often associated with Japanese culture. In modern usage, the word "origami" is used as an inclusive term for all folding practices, regardless of their culture of origin. The goal is to transform a flat square sheet of paper into a finished sculpture through folding and sculpting techniques. Modern origami practitioners generally discourage the use of cuts, glue, or markings on the paper. Origami folders often use the Japanese word kirigami to refer to designs which use cuts.

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.

Erik Demaine Professor of Computer Science

Erik D. Demaine is a professor of Computer Science at the Massachusetts Institute of Technology and a former child prodigy.

Net (polyhedron) arrangement of joined polytopes which can be folded to become the facets of a higher-dimensional polytope

In geometry a net of a polyhedron is an arrangement of non-overlapping edge-joined polygons in the plane which can be folded to become the faces of the polyhedron. Polyhedral nets are a useful aid to the study of polyhedra and solid geometry in general, as they allow for physical models of polyhedra to be constructed from material such as thin cardboard.

In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of subsets of vertices of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness, vertex separation number, or node searching number.

Toshikazu Kawasaki Japanese paperfolder

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. Kawasaki also teaches Mathematics at Sasebo Technical Junior College.

Antiparallelogram quadrilateral with two pairs of opposite equal-length sides, the longer two of which are crossed

In geometry, an antiparallelogram is a quadrilateral having, like a parallelogram, two opposite pairs of equal-length sides, but in which the sides of one pair cross each other. The longer of the two pairs will always be the one that crosses. Antiparallelograms are also called contraparallelograms or crossed parallelograms.

Disphenoid tetrahedron whose four faces are congruent acute-angled triangles

In geometry, a disphenoid is a tetrahedron whose four faces are congruent acute-angled triangles. It can also be described as a tetrahedron in which every two edges that are opposite each other have equal lengths. Other names for the same shape are sphenoid, bisphenoid, isosceles tetrahedron, equifacial tetrahedron, almost regular tetrahedron, and tetramonohedron.

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

Joseph O'Rourke is the Spencer T. and Ann W. Olin Professor of Computer Science at Smith College and the founding chair of the Smith computer science department. His main research interest is computational geometry.

In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the (simple) 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs. Branko Grünbaum has called this theorem “the most important and deepest known result on 3-polytopes.”

Rigid origami is a branch of origami which is concerned with folding structures using flat rigid sheets joined by hinges. That is, unlike with paper origami, the sheets cannot bend during the folding process; they must remain flat at all times. However, there is no requirement that the structure start as a single flat sheet – for instance shopping bags with flat bottoms are studied as part of rigid origami.

The napkin folding problem is a problem in geometry and the mathematics of paper folding that explores whether folding a square or a rectangular napkin can increase its perimeter. The problem is known under several names, including the Margulis napkin problem, suggesting it is due to Grigory Margulis, and the Arnold's rouble problem referring to Vladimir Arnold and the folding of a Russian ruble bank note. Some versions of the problem were solved by Robert J. Lang, Svetlana Krat, Alexey S. Tarasov, and Ivan Yaschenko. One form of the problem remains open.

In the mathematics of paper folding, map folding and stamp folding are two problems of counting the number of ways that a piece of paper can be folded. In the stamp folding problem, the paper is a strip of stamps with creases between them, and the folds must lie on the creases. In the map folding problem, the paper is a map, divided by creases into rectangles, and the folds must again lie only along these creases.

The fold-and-cut theorem states that any shape with straight sides can be cut from a single (idealized) sheet of paper by folding it flat and making a single straight complete cut. Such shapes include polygons, which may be concave, shapes with holes, and collections of such shapes.

The Alexandrov uniqueness theorem is a rigidity theorem in mathematics, describing three-dimensional convex polyhedra in terms of the distances between points on their surfaces. It implies that convex polyhedra with distinct shapes from each other also have distinct metric spaces of surface distances, and it characterizes the metric spaces that come from the surface distances on polyhedra. It is named after Soviet mathematician Aleksandr Danilovich Aleksandrov, who published it in the 1940s.

Jun Maekawa is a Japanese software engineer, mathematician, and origami artist. He is known for popularizing the method of utilizing crease patterns in designing origami models, with his 1985 publication Viva Origami, as well as other paperfolding-related theorems and mathematical analysis. One of them being Maekawa's theorem in relation to the flat-foldability of origami models.

Maekawas theorem

Maekawa's theorem is a theorem in the mathematics of paper folding named after Jun Maekawa. It relates to flat-foldable origami crease patterns and states that at every vertex, the numbers of valley and mountain folds always differ by two in either direction. The same result was also discovered by Jacques Justin and, even earlier, by S. Murata.

Anna Lubiw is a computer scientist known for her work in computational geometry and graph theory. She is currently a professor at the University of Waterloo.

Geometric Folding Algorithms: Linkages, Origami, Polyhedra is a monograph on the mathematics and computational geometry of mechanical linkages, paper folding, and polyhedral nets, by Erik Demaine and Joseph O'Rourke. It was published in 2007 by Cambridge University Press (ISBN 978-0-521-85757-4). A Japanese-language translation by Ryuhei Uehara was published in 2009 by the Modern Science Company (ISBN 978-4-7649-0377-7).

References

  1. 1 2 3 Hull, Thomas C. (2015), "Coloring connections with counting mountain-valley assignments", Origami6, Volume I: Mathematics, Providence, Rhode Island: American Mathematical Society, pp. 3–10, arXiv: 1601.02727 , MR   3494912
  2. 1 2 3 Demaine, Erik; O'Rourke, Joseph (2007), "12.2.2 Flat-Foldable Single-Vertex Mountain–Valley Patterns", Geometric Folding Algorithms, Cambridge University Press, pp. 203–210, ISBN   978-0-521-71522-5 ; see in particular Lemma 12.2.5, p. 204
  3. Demaine & O'Rourke (2007), Lemma 12.2.8, p. 205.
  4. Bern, Marshall; Hayes, Barry (1996), "The complexity of flat origami", Proceedings of the Seventh Annual ACM–SIAM Symposium on Discrete Algorithms (Atlanta, GA, 1996), New York: ACM, pp. 175–183, MR   1381938
  5. Demaine & O'Rourke (2007), Theorem 12.2.9 and Corollary 12.2.10, p. 207.
  6. 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 Demaine & O'Rourke (2007).
  7. Justin, J. (1994), "Towards a mathematical theory of origami", 2nd Int. Meeting of Origami Science, Otsu, Japan. As cited by Demaine & O'Rourke (2007).