Computational Geometry Books

Computational Geometry: Algorithms and Applications — Mark de Berg, Otfried Cheong, Marc van Kreveld & Mark Overmars (Springer-Verlag 2008, 3rd ed., ISBN 978-3-540-77973-5)

This book has a well-deserved reputation as the best guide to its field. The authors lucidly explain a broad selection of standard algorithms and data structures, including real-world motivations, numerous visualizations, and snippets of pseudocode. There’s just one problem: the cognitive distance between an intuitive understanding of geometric algorithms and their actual programming is enormous. Computers only manipulate numbers, not shapes. Bridging this fundamental gap requires a surprising amount of effort, especially once you consider tricky issues like floating-point imprecision or run-time performance. De Berg et al. provide very little help here, and you might well despair trying to build working implementations of these nicely presented algorithms.

One option is to search the Internet for existing implementations, e.g. in my own Tektosyne library. The other is to obtain two older books, Computational Geometry and Computer Graphics in C++ by Michael J. Laszlo (Prentice-Hall 1996, ISBN 0-13-290842-5) and Computational Geometry in C by Joseph O’Rourke (Cambridge University Press 1998, 2nd ed., ISBN 0-521-64976-5). To my knowledge, these are the last printed books on computational geometry that include concrete working code. They cannot replace de Berg et al. as their coverage is relatively fragmentary, but they are invaluable as a demonstration of how to move geometric algorithms from specification to implementation.

2016-06-21: The second edition of Algorithms in a Nutshell by Heineman et al. has greatly expanded its coverage of computational geometry and now includes working code for spatial tree structures and Voronoi diagrams, in addition to convex hulls and line-segment intersections. This should now be your starting point if you’re looking for implementations.

(See Developer Books for my complete review archive.)

Leave a Reply