Discrete and Computational Geometry
Satyan L. Devadoss & Joseph O’Rourke
[Full disclosure: Princeton Press kindly sent me a free review copy of this book, and Satyan Devadoss is a (former) teacher and (current) good friend of mine. I was the TA for the first incarnation of the computational geometry class Devadoss taught at Williams College, the lecture notes of which probably ended up forming the basis of (at least parts of) this book. Decide for yourself whether you think I’m biased—though note that if I honestly didn’t like a book that a friend wrote, I’d be much more likely to not say anything at all than to lie about it on the Internet!]
Discrete geometry focuses on discrete, finite sets of things like points, lines, triangles, polygons, and polyhedra, rather than on continuous things like smooth surfaces. Computational geometry focuses on the problems and techniques inherent in using computers to work with geometrical objects and data—something with tons of applications including architecture, design, planning and infrastructure, robotics, geography and cartography, medicine… basically anything where you want to use computers to help accomplish something in the physical world! Since computers are inherently discrete, the two subjects fit naturally together, and there is a lot of interplay between the theoretical and the practical. This book covers some basic topics in these areas (and, just for fun, also touches on a few research topics), with chapters on polygons, convex hulls, triangulations, Voronoi diagrams, curves, polyhedra, and configuration spaces. It does a great job making the subject lively, exciting, and accessible, and still manages to include lots of detail and depth. I was not particularly interested in the subject area before starting, but I got sucked in—the book is chock-full of beautiful, surprising results (many with cool applications).
This really is an undergraduate textbook, and not the sort of popular math book that I typically review here—but in fact it does have some of the flavor of a popular math book (with a lot more exercises thrown in). While it’s not the sort of thing to curl up with in a coffee shop (though I did read it on the bus!) it will richly reward the interested amateur. The fact that it’s designed as an undergraduate textbook should give you an idea of the required background—nothing particularly deep, just a solid grasp of algebra and geometry, and perhaps a bit of basic graph theory. There is a tiny bit of calculus but those sections can safely be skipped.
I should also mention the illustrations (as everyone knows, I’m a sucker for pretty pictures!). Of course it would be impossible to write a book about geometry without including pictures, but the beautiful full-color illustrations on almost every page of this book go well beyond the bare minimum; they form an integral and enlivening part of the presentation. (I would expect no less from Satyan.) It’s almost worth getting the book just to flip through the pages and ooh and aah over the illustrations. Though if you did that you’d probably get sucked into reading it too.