Geometry Algorithm Textbooks

These are recommended textbooks that could be used for teaching a geometry algorithms course. They are expository, follow a logical progression, and have student-oriented exercises. Some are better than others. Some are introductory, and some are advanced. Some are math and theory oriented, and some are algorithmic and practical implementation oriented. Overall, for an introductory course focusing on geometry algorithms, we recommend either Computational Geometry in C (by O'Rourke) or Computational Geometry : Algorithms and Applications (by de Berg et al). However, a more advanced course or a different focus, like a computer graphics course, would use a different text. Each teacher has to make their own final choice.


(2001)		Introduction to Algorithms (2nd Edition) by Thomas Corman, Charles Leiserson, Ronald Rivest, Clifford Stein
		New: $71.05 List: ~~$82.00~~ Buy Used from: $58.99

	This is the bible for general algorithms. The correctness of all algorithms is clearly demonstrated, there are sample applications, and every algorithm is given in pseudo-code. There is a huge list of topics that goes well beyond sorting and searching to graph theory and computational geometry plus much more. This is the best modern comprehensive fundamentals book for algorithms.


(2000)		Computational Geometry : Algorithms and Applications (2nd Edition) by Mark de Berg, Marc van Kreveld, Mark Overmars, & O. Schwarzkopf
		New: $40.40 List: ~~$49.95~~ Buy Used from: $34.21

	An excellent textbook with detailed coverage of a large variety of algorithms. This and O'Rourke's book are the main contenders for the textbook of choice for a course. In reality, they compliment each other with their slightly different points of view, and each has its own unique material. This text is slightly more structured than O'Rourke's which is more free flowing. Both are first rate, and represent the current state of geometry algorithms.


(1998)		Computational Geometry in C (2nd Edition) by Joseph O'Rourke
		New: $37.60 List: ~~$42.00~~ Buy Used from: $28.25

	A great book. It both presents a wide variety of essential algorithms, and also includes detailed implementations in "C" with concern for the fine points. It is not just a cookbook, as many code-oriented books are, but encourages creative problem-solving thinking, often comparing and discussing multiple algorithmic approaches to the same problem. It is a must-read by all serious practitioners, and is a great text for an intermediate level course. Code from the book can be downloaded from the author's site: Computational Geometry in C.


(1998)		Algorithmic Geometry by Jean-Daniel Boissonnat & Mariette Yvinec
		New: $160.00 Buy Used from: $110.00

	This book presents a systematic treatment of the foundations of computational geometry and presents rigorous algorithmic solutions that are efficient in practical situations. This is a clearly written book that goes into considerable depth on many topics not found elsewhere (like 3D triangulation). It is highly recommended, but not for the beginner; and could be used for an advanced course about geometry algorithms.


(1997)		The Algorithm Design Manual by Steve Skiena
		New: $63.96 List: ~~$79.95~~ Buy Used from: $45.00

	More than just an outstanding cookbook, this book gives you a method of attack for designing new algorithms with "War Stories" illustrating the author's approach. It includes detailed discussions of 75 significant and interesting algorithms including 16 for computational geometry and 23 for graph theory (both P and NP). Code for algorithms discussed in the book are on an included CD, or can be downloaded from The Stony Brook Algorithm Repository.


(1995)		Computational Geometry and Computer Graphics in C++ by Michael Laszlo
		New: $73.60 List: ~~$92.00~~ Buy Used from: $16.99

	This book is a bit flawed, but there's a good variety of basic topics. The presentation never gets too advanced which is both good and bad: things never get overly complicated, but then one stops short of understanding the best algorithms. Also, there is a lack of good exposition of the basic concepts involved. However, it does have C++ code for everything. The book is organized to cover incremental, plane-sweep, divide-and-conquer, and spatial subdivision algorithm approaches, with numerous examples of each.


(1994)		Computational Geometry through Randomized Algorithms by Ketan Mulmuley
		New: $58.00 Buy Used from: $43.95

	This book is a concise introduction to computational geometry using randomized methods by one of the outstanding researchers in this field. Although it seems specialized, this method is currently a successful practical approach for implementing many geometry algorithms, including: computing trapezoidal decompositions, Voronoi diagrams, point location and range queries in arrangements of hyperplanes, constructing convex polytopes, and hidden surface removal. This is a well-written graduate-level textbook.


(1987)		Algorithms in Combinatorial Geometry by Herbert Edelsbrunner
		New: $129.00 Buy Used from: $59.99

	This is a polished advanced text about computational geometry algorithms and their connection with the older field of combinatorial geometry. The emphasis of the book is on arrangements and computational geometry in arbitrary dimensions, and this text is considered the best book on that topic. It is organized into 3 parts: I. Combinatorial Geometry, II. Fundamental Geometric Algorithms, and III. Geometric and Algorithmic Applications. There is a good variety of standard topics: arrangements, dissections, convex hulls, skeletons, planar point location, visibility graphs, Voronoi diagrams, Delaunay triangulations, and more. All algorithms are given in clear structured pseudo-code, and supporting mathematics is presented with proofs. The exercises are outstanding and ordered in difficulty from 1 (easy) to 5 (an unsolved problem). This would be a terrific text for an advanced graduate class.


(1985)		Computational Geometry: An Introduction by Franco Preparata & Michael Shamos
		New: $71.96 List: ~~$99.00~~ Buy Used from: $60.00

	This book elaborates and expands on Shamos' Ph.D. Thesis (1978) [Preparata was his advisor] which is said to mark the start of modern algorithmic "computational geometry". This book is the foundation of the field, and presents a large collection of fundamental geometry algorithms and techniques. Although some of the algorithms have been improved over time, they are all viable, and some are still unsurpassed. This book is written in a fairly rigorous style, and may be better used as a secondary reference to the texts of O'Rourke or de Berg which are more pedagogical.


(1983)		A Programmer's Geometry by Adrian Bowyer & John Woodwark
		New: Out of Stock List: $32.95 Buy Used from: $33.75

	This is a classic book with algorithms for the most elementary Euclidean constructions. Even 20 years after its publication, it is a very useful basic reference work.