Geometric Folding Algorithms

Last updated

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). [1] [2] [3] [4] A Japanese-language translation by Ryuhei Uehara was published in 2009 by the Modern Science Company ( ISBN   978-4-7649-0377-7). [5]

Contents

Audience

Although aimed at computer science and mathematics students, [3] [4] much of the book is accessible to a broader audience of mathematically-sophisticated readers with some background in high-school level geometry. [2] [4] Mathematical origami expert Tom Hull has called it "a must-read for anyone interested in the field of computational origami". [6] It is a monograph rather than a textbook, and in particular does not include sets of exercises. [4]

The Basic Library List Committee of the Mathematical Association of America has recommended this book for inclusion in undergraduate mathematics libraries. [1]

Topics and organization

The book is organized into three sections, on linkages, origami, and polyhedra. [1] [2]

Topics in the section on linkages include the Peaucellier–Lipkin linkage for converting rotary motion into linear motion, [4] Kempe's universality theorem that any algebraic curve can be traced out by a linkage, [1] [4] the existence of linkages for angle trisection, [1] and the carpenter's rule problem on straightening two-dimensional polygonal chains. [4] This part of the book also includes applications to motion planning for robotic arms, and to protein folding. [1] [2]

The second section of the book concerns the mathematics of paper folding, and mathematical origami. It includes the NP-completeness of testing flat foldability, [2] the problem of map folding (determining whether a pattern of mountain and valley folds forming a square grid can be folded flat), [2] [4] the work of Robert J. Lang using tree structures and circle packing to automate the design of origami folding patterns, [2] [4] the fold-and-cut theorem according to which any polygon can be constructed by folding a piece of paper and then making a single straight cut, [2] [4] origami-based angle trisection, [4] rigid origami, [2] and the work of David A. Huffman on curved folds. [4]

In the third section, on polyhedra, the topics include polyhedral nets and Dürer's conjecture on their existence for convex polyhedra, the sets of polyhedra that have a given polygon as their net, Steinitz's theorem characterizing the graphs of polyhedra, Cauchy's theorem that every polyhedron, considered as a linkage of flat polygons, is rigid, and Alexandrov's uniqueness theorem stating that the three-dimensional shape of a convex polyhedron is uniquely determined by the metric space of geodesics on its surface. [4]

The book concludes with a more speculative chapter on higher-dimensional generalizations of the problems it discusses. [4]

Related Research Articles

Dual polyhedron

In geometry, any polyhedron is associated with a second dual figure, where the vertices of one correspond to the faces of the other and the edges between pairs of vertices of one correspond to the edges between pairs of faces of the other. Such dual figures remain combinatorial or abstract polyhedra, but not all are also geometric polyhedra. Starting with any given polyhedron, the dual of its dual is the original polyhedron.

Polyhedron Three-dimensional shape with flat polygonal faces, straight edges and sharp corners

In geometry, a polyhedron is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices. The word polyhedron comes from the Classical Greek πολύεδρον, as poly- + -hedron.

4-polytope Four-dimensional geometric object with flat sides

In geometry, a 4-polytope is a four-dimensional polytope. It is a connected and closed figure, composed of lower-dimensional polytopal elements: vertices, edges, faces (polygons), and cells (polyhedra). Each face is shared by exactly two cells.

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.

Modular origami

Modular origami or unit origami is a paperfolding technique which uses two or more sheets of paper to create a larger and more complex structure than would be possible using single-piece origami techniques. Each individual sheet of paper is folded into a module, or unit, and then modules are assembled into an integrated flat shape or three-dimensional structure, usually by inserting flaps into pockets created by the folding process. These insertions create tension or friction that holds the model together.

Discrete geometry Branch of geometry that studies combinatorial properties and constructive methods

Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.

Net (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.

Polyhedron model

A polyhedron model is a physical construction of a polyhedron, constructed from cardboard, plastic board, wood board or other panel material, or, less commonly, solid material.

Antiparallelogram

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 as in a scissors mechanism. The longer of the two pairs will always be the one that crosses. Antiparallelograms are also called contraparallelograms or crossed parallelograms.

Cauchy's theorem is a theorem in geometry, named after Augustin Cauchy. It states that convex polytopes in three dimensions with congruent corresponding faces must be congruent to each other. That is, any polyhedral net formed by unfolding the faces of the polyhedron onto a flat surface, together with gluing instructions describing which faces should be connected to each other, uniquely determines the shape of the original polyhedron. For instance, if six squares are connected in the pattern of a cube, then they must form a cube: there is no convex polyhedron with six square faces connected in the same way that does not have the same shape.

Flexible polyhedron

In geometry, a flexible polyhedron is a polyhedral surface that allows continuous non-rigid deformations such that all faces remain rigid. The Cauchy rigidity theorem shows that in dimension 3 such a polyhedron cannot be convex.

Edge (geometry)

In geometry, an edge is a particular type of line segment joining two vertices in a polygon, polyhedron, or higher-dimensional polytope. In a polygon, an edge is a line segment on the boundary, and is often called a side. In a polyhedron or more generally a polytope, an edge is a line segment where two faces meet. A segment joining two vertices while passing through the interior or exterior is not an edge but instead is called a diagonal.

Bricard octahedron

In geometry, a Bricard octahedron is a member of a family of flexible polyhedra constructed by Raoul Bricard in 1897. That is, it is possible for the overall shape of this polyhedron to change in a continuous motion, without any changes to the lengths of its edges nor to the shapes of its faces. These octahedra were the first flexible polyhedra to be discovered.

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

Toroidal polyhedron

In geometry, a toroidal polyhedron is a polyhedron which is also a toroid, having a topological genus of 1 or greater. Notable examples include the Császár and Szilassi polyhedra.

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.

A History of Folding in Mathematics: Mathematizing the Margins is a book in the history of mathematics on the mathematics of paper folding. It was written by Michael Friedman and published in 2018 by Birkhäuser as volume 59 of their Historial Studies series.

Origami Polyhedra Design is a book on origami designs for constructing polyhedra. It was written by origami artist and mathematician John Montroll, and published in 2009 by A K Peters.

Convex Polyhedra is a book on the mathematics of convex polyhedra, written by Soviet mathematician Aleksandr Danilovich Aleksandrov, and originally published in Russian in 1950, under the title Выпуклые многогранники. It was translated into German by Wilhelm Süss as Konvexe Polyeder in 1958. An updated edition, translated into English by Nurlan S. Dairbekov, Semën Samsonovich Kutateladze and Alexei B. Sossinsky, with added material by Victor Zalgaller, L. A. Shor, and Yu. A. Volkov, was published as Convex Polyhedra by Springer-Verlag in 2005.

References

  1. 1 2 3 4 5 6 Carbno, Collin (May 2009), "Review of Geometric Folding Algorithms", MAA Reviews, Mathematical Association of America
  2. 1 2 3 4 5 6 7 8 9 Paquete, Luís (November 2009), "Review of Geometric Folding Algorithms", European Journal of Operational Research, 199 (1): 311–313, doi:10.1016/j.ejor.2008.06.009
  3. 1 2 mbec (2011), "Review of Geometric Folding Algorithms", EMS Reviews, European Mathematical Society
  4. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Fasy, Brittany Terese; Millman, David L. (March 2011), "Review of Geometric Folding Algorithms", SIGACT News, Association for Computing Machinery, 42 (1): 43–46, doi:10.1145/1959045.1959056, S2CID   6514501
  5. Uehara, Ryuhei, 幾何的な折りアルゴリズム リンケージ・折り紙・多面体 , retrieved 2020-02-02
  6. Hull, Tom (2012), "Other sources", Project Origami: Activities for Exploring Mathematics (2nd ed.), CRC Press, p. xviii