Introduction to Computational Origami

The field of computational origami has to do with questions we can ask about paper folding that are computational in nature. For example, given a collection of crease lines drawn on a piece of paper, how can we tell if exactly these creases can be used to fold the paper into a flat object?  In 1996 Bern and Hayes proved that this problem is NP-hard, and in doing so paved the way for numerous researchers to investigate other computational problems having to do with folding (and unfolding) processes. This subject lives in the larger field of computational geometry, and the first major reference appeared in 2007 with the publication of Geometric Folding Algorithms by Erik Demaine and Joseph O'Rourke.

 

The book under review, Introduction to Computational Origami, is a research monograph that complements previous references on the subject well. Rather than surveying the whole field, as the Demaine and O'Rourke book does, Uehara focuses on a few key topics:  Polyhedral net unfolding, 1-dimensional stamp folding, and more recent topics such as petal and bumpy pyramid folding, zipper-unfolding of polyhedra, and rep-cubes (polyominoes that are a net of a cube that can be subdivided into identical polyominoes, each of which is also the net of a cube). 

 

The treatment given for each of these topics offers a look into the current and engaging research. For example, the ways in which a polyhedron can be unfolded, usually by cutting along the edges, into a connected chain of polygons that lies in the plane without overlapping, called a net of the polyhedron, has been studied since the 1500s. It is surprising that whether or not all convex polyhedra have nets is still an open question. The book under review presents new investigations, such as whether a single net can be folded in different ways to make different polyhedra. For example, can we find a single net that could fold into a tetrahedron following one set of crease lines and into a cube following another set of crease lines?  This book proves that it is impossible if we insist on cutting the polyhedra only along their edges, called an edge-unfolding. If we instead allow cuts that cross faces of the cube and regular tetrahedron, then it is an open question whether or not such a net exists. On the other hand, given two rectangular prisms R1 and R2 with the same surface area, can we find a net, where cutting through faces is allowed, that can fold into R1 and R2?  The answer is yes, and three different algorithms for producing such a net are described. These results and open questions are surprising, delightful, and well-illustrated in this book. A smattering of exercises is also included, with answers in the back of the book.

 

A major flaw of this book must be mentioned, although it is no fault of the author. This book was originally published in Japanese in 2018. The 2020 translation has some updates, for example including references to papers from 2019. But the publisher clearly did not employ a copy editor to correct the use of English. As a result, nearly every paragraph has grammatical flaws, and this introduces imprecision that can make the mathematics difficult to follow at times. Anyone already familiar with the topics of polyhedral nets, computational complexity, and computational geometry will have little trouble understanding this text. But students or those wishing to learn about this area without prior background might be lost at times, despite the fact that the book is intended to be understandable by an audience with a basic undergraduate-level understanding of mathematics and theoretical computer science. Any amount of copy editing would have been a great help.

---

 

Thomas C. Hull (thull@wne.edu) is an Associate Professor at Western New England University in Springfield, MA.