Fold-and-cut theorem

Last updated

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. [1] Such shapes include polygons, which may be concave, shapes with holes, and collections of such shapes (i.e. the regions need not be connected).

Contents

The corresponding problem that the theorem solves is known as the fold-and-cut problem, which asks what shapes can be obtained by the so-called fold-and-cut method. A particular instance of the problem, which asks how a particular shape can be obtained by the fold-and-cut method, is known as a fold-and-cut problem.

History

The earliest known description of a fold-and-cut problem appears in Wakoku Chiyekurabe (Mathematical Contests), a book that was published in 1721 by Kan Chu Sen in Japan. [2]

An 1873 article in Harper's New Monthly Magazine describes how Betsy Ross may have proposed that stars on the American flag have five points, because such a shape can easily be obtained by the fold-and-cut method. [3]

In the 20th century, several magicians published books containing examples of fold-and-cut problems, including Will Blyth, [4] Harry Houdini, [5] and Gerald Loe (1955). [6]

Inspired by Loe, Martin Gardner wrote about the fold-and-cut problems in Scientific American in 1960. Examples mentioned by Gardner include separating the red squares from the black squares of a checkerboard with one cut, and "an old paper-cutting stunt, of unknown origin" in which one cut splits a piece of paper into both a Latin cross and a set of smaller pieces that can be rearranged to spell the word "hell". Foreshadowing work on the general fold-and-cut theorem, he writes that "more complicated designs present formidable problems". [7]

Creating a Koch snowflake curve by the fold-and-cut method FoldedKoch.gif
Creating a Koch snowflake curve by the fold-and-cut method

The first proof of the fold-and-cut theorem, solving the problem, was published in 1999 by Erik Demaine, Martin Demaine, and Anna Lubiw. [8] [9]

Solutions

There are two general methods known for solving instances of the fold-and-cut problem, based on straight skeletons and on circle packing respectively.

Related Research Articles

<span class="mw-page-title-main">Martin Gardner</span> American mathematics and science writer (1914–2010)

Martin Gardner was an American popular mathematics and popular science writer with interests also encompassing scientific skepticism, micromagic, philosophy, religion, and literature – especially the writings of Lewis Carroll, L. Frank Baum, and G. K. Chesterton. He was also a leading authority on Lewis Carroll. The Annotated Alice, which incorporated the text of Carroll's two Alice books, was his most successful work and sold over a million copies. He had a lifelong interest in magic and illusion and in 1999, MAGIC magazine named him as one of the "100 Most Influential Magicians of the Twentieth Century". He was a prolific and versatile author, publishing more than 100 books.

<span class="mw-page-title-main">Polyomino</span> Geometric shapes formed from squares

A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. It is a polyform whose cells are squares. It may be regarded as a finite subset of the regular square tiling.

<span class="mw-page-title-main">Flexagon</span> Paper model

In geometry, flexagons are flat models, usually constructed by folding strips of paper, that can be flexed or folded in certain ways to reveal faces besides the two that were originally on the back and front.

<span class="mw-page-title-main">Mathematics of paper folding</span> Overview of the mathematics of paper folding

The discipline 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 up-to cubic mathematical equations.

<span class="mw-page-title-main">Polycube</span> Shape made from cubes joined together

A polycube is a solid figure formed by joining one or more equal cubes face to face. Polycubes are the three-dimensional analogues of the planar polyominoes. The Soma cube, the Bedlam cube, the Diabolical cube, the Slothouber–Graatsma puzzle, and the Conway puzzle are examples of packing problems based on polycubes.

<span class="mw-page-title-main">Erik Demaine</span> Professor of computer science

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

<span class="mw-page-title-main">Net (polyhedron)</span> Edge-joined polygons which fold into a polyhedron

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.

The crossed ladders problem is a puzzle of unknown origin that has appeared in various publications and regularly reappears in Web pages and Usenet discussions.

<span class="mw-page-title-main">Straight skeleton</span> Method in geometry for representing a polygon by a topological skeleton

In geometry, a straight skeleton is a method of representing a polygon by a topological skeleton. It is similar in some ways to the medial axis but differs in that the skeleton is composed of straight line segments, while the medial axis of a polygon may involve parabolic curves. However, both are homotopy-equivalent to the underlying polygon.

<span class="mw-page-title-main">Rigid origami</span>

Rigid origami is a branch of origami which is concerned with folding structures using flat rigid sheets joined by hinges. That is, unlike in traditional origami, the panels of the paper cannot be bent during the folding process; they must remain flat at all times, and the paper only folded along its hinges. A rigid origami model would still be foldable if it was made from glass sheets with hinges in place of its crease lines.

<span class="mw-page-title-main">Martin Demaine</span> American artist and mathematician

Martin L. (Marty) Demaine is an artist and mathematician, the Angelika and Barton Weller artist in residence at the Massachusetts Institute of Technology (MIT).

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.

In a publishing career spanning 80 years (1930–2010), popular mathematics and science writer Martin Gardner (1914–2010) authored or edited over 100 books and countless articles, columns and reviews.

Gathering 4 Gardner (G4G) is an educational foundation and non-profit corporation devoted to preserving the legacy and spirit of prolific writer Martin Gardner. G4G organizes conferences where people who have been inspired by or have a strong personal connection to Martin Gardner can meet and celebrate his influence. These events explore ideas and developments in recreational mathematics, magic, illusion, puzzles, philosophy, and rationality, and foster creative work in all of these areas by enthusiasts of all ages. G4G also facilitates a related series of events called Celebration of Mind (CoM).

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.

David Anthony Klarner was an American mathematician, author, and educator. He is known for his work in combinatorial enumeration, polyominoes, and box-packing.

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

<span class="mw-page-title-main">Blooming (geometry)</span>

In the geometry of convex polyhedra, blooming or continuous blooming is a continuous three-dimensional motion of the surface of the polyhedron, cut to form a polyhedral net, from the polyhedron into a flat and non-self-overlapping placement of the net in a plane. As in rigid origami, the polygons of the net must remain individually flat throughout the motion, and are not allowed to intersect or cross through each other. A blooming, reversed to go from the flat net to a polyhedron, can be thought of intuitively as a way to fold the polyhedron from a paper net without bending the paper except at its designated creases.

In computational geometry, the source unfolding of a convex polyhedron is a net obtained by cutting the polyhedron along the cut locus of a point on the surface of the polyhedron. The cut locus of a point consists of all points on the surface that have two or more shortest geodesics to . For every convex polyhedron, and every choice of the point on its surface, cutting the polyhedron on the cut locus will produce a result that can be unfolded into a flat plane, producing the source unfolding. The resulting net may, however, cut across some of the faces of the polyhedron rather than only cutting along its edges.

Thomas Malin Rodgers was an Atlanta-based businessman and puzzle collector who is remembered as the originator of the Gathering 4 Gardner (G4G) educational foundation, first conceived in 1992. He co-founded G4G with magician and toy inventor Mark Setteducati and UC Berkeley professor Elwyn Berlekamp. Over the past three decades it hosted 14 biennial conferences for aficionados of the recreational mathematician and Scientific American columnist and writer Martin Gardner. Rodgers also edited 6 volumes of Martin Gardner tribute books, published by AK Peters. Rodgers' personal physical puzzle collection was legendary.

References

  1. Demaine, Erik D.; Demaine, Martin L. (2004), "Fold-and-Cut Magic", Tribute to a Mathemagician, A K Peters, pp. 23–30.
  2. The Fold-and-Cut Problem: Kan Chu Sen's Wakoku Chiyekurabe, Erik Demaine, 2010, retrieved 2013-10-20.
  3. Osgood, Kate Putnam (1873), "National standards and emblems", Harper's, 47 (278): 171–181, Mrs. Ross expressed her willingness to make the flag, but suggested that the stars would be more symmetrical and pleasing to the eye if made with five points, and she showed them how such a star could be made, by folding a sheet of paper and producing the pattern by a single cut.
  4. Blyth, Will (1920), Paper magic : being a collection of entertaining and amusing models, toys, puzzles, conjuring tricks, etc., in which paper is the only or principle material required, London: C. Arthur Pearson.
  5. Houdini, Harry (1922), Houdini's paper magic; the whole art of performing with paper, including paper tearing, paper folding and paper puzzles, New York: E.P. Dutton & company.
  6. Loe, Gerald M. (1955), Paper Capers, Chicago, Illinois: Magic.
  7. Gardner, Martin (June 1960), "Paper cutting", Scientific American . Reprinted with additional material as Chapter 5 of Martin Gardner's New Mathematical Diversions from Scientific American, Simon & Schuster, 1966, pp. 58–69.
  8. Demaine, Erik D.; Demaine, Martin L.; Lubiw, Anna (1999), "Folding and one straight cut suffice", Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '99), pp. 891–892.
  9. O'Rourke, Joseph (2013), How to Fold It, Cambridge University Press, p. 144, ISBN   9781139498548 .