Geometric Folding Algorithms

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]

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]

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]

• Authors' web site for Geometric Folding Algorithms including contents, errata, and advances on open problems