You are here

Discrete and Computational Geometry

Satyan L. Devadoss and Joseph O'Rourke
Princeton University Press
Publication Date: 
Number of Pages: 
BLL Rating: 

The Basic Library List Committee strongly recommends this book for acquisition by undergraduate mathematics libraries.

[Reviewed by
Bill Wood
, on

Discrete and computational geometry is relatively new field in mathematics and a delightful playground for exploring the interplays between discrete and coninuous phenomena and between theory and implementation. When studying the geometry of discrete objects (point sets, graphs, polyhedra, and such), we find that most classical ideas from geometry apply in some form but are accessed through the object’s combinatorial features. We also find some wide gaps between proving something exists and algorithmically constructing it.

This is a fantastic area for undergraduate independent study and research. There are hard theorems to prove, but there are plenty of opportunities to carve out problems on which an undergraduate can make meaningful progress by exploring special cases, finding bounds, or running computer experiments.

Devadoss and O’Rourke offer an outstanding introduction to the concepts, techniques, and research in the field. The material is broadly accessible with no real prerequisites beyond the usual tolerance for mathematical notation and proof. Nonetheless, the reader is ready to consider the first of many unsolved problems on page 6 (find criteria for tetrahedralizability). There are 29 unsolved problems distributed throughout the book along with plenty of interesting exercises of varying difficulty (including some indicated as being at a modern research level). The accessibility does come at the cost of some detail and rigor, but the book is written as an invitation for the reader to fill most of that in him or herself. Annotated suggested readings at the end of each chapter help with this effort.

There are beautifully designed color figures on almost every page. Great care was taken to create exactly the right picture to convey an idea. Color is also used in the text in a way that genuinely helps navigation.

Much of the content is standard for the field — including art gallery theorems, triangulations, convex hulls, Delaunay triangulations and Voroni diagrams, Euler’s formula for polyhedra, motion planning — but the presentation is anything but ordinary. (These topics are familiar from the second author’s classic Computational Geometry in C, but with a different viewpoint) . The text also includes considerable material on less standard topics reflecting the authors’ expertise including geometric unfolding (O’Rourke has some other recent books on this topic as well) and associahedra (Devadoss), much of which has not been packaged into a text like this before.

As an example of the kind of tours the book takes, one ambitious effort discusses curve shortening by first explaining it in terms of flows on the heat equation and then interpreting the idea discretely — getting all the way to a cursory discussion of Ricci flow and the Poincaré Conjecture. Details are sketchy, of course, but the reader is exposed to how mathematicians extend and apply ideas to prove new results. This is one example of taking a classical concept (the derivative in this case) and figuring out what it means in a discrete setting, an important skill in this field specifically but also in more general mathematics. (This example is the only instance where the reader might need anything as sophisticated as calculus.)

The material intersects with computer science, but no formal programming experience is required. Algorithms are discussed in a way that is friendly to the computer science novice, with narrative descriptions and no pseudocode. The reader who wants to jump in and code will have lots of theory in hand here but no data structures or code samples.

The publisher’s website includes errata (worth reviewing — some of the errors are non-trivial) and offers a solution manual to instructors. The manual offers some succinct combination of solutions, hints, references, and commentary for each exercise.

Devadoss and O’Rourke’s Discrete and Computational Geometry is a rare gem, inviting the mathematical novice to real problems in contemporary mathematics and going into a surprising amount of depth with very little background. It could be used as a text for an undergraduate course in mathematics or computer science or as a supplement to a variety of courses in these disciplines, including geometry, algorithms, or discrete mathematics. It is also a terrific source for undergraduate projects or a friendly introduction for professionals looking for new territory. It is one of the best produced books this reviewer has ever seen and a delight to read.

Bill Wood is an Assistant Professor of Mathematics at the University of Northern Iowa.