Computational Geometry: Algorithms and Applications

This well-accepted introduction to computational geometry is a textbook for high-level undergraduate and low-level graduate courses. The focus is on algorithms and hence the book is well suited for students in computer science and engineering. Motivation is provided from the application areas: all solutions and techniques from computational geometry are related to particular applications in robotics, graphics, CAD/CAM, and geographic information systems. For students this motivation will be especially welcome. Modern insights in computational geometry are used to provide solutions that are both efficient and easy to understand and implement. All the basic techniques and topics from computational geometry, as well as several more advanced topics, are covered. The book is largely self-contained and can be used for self-study by anyone with a basic background in algorithms.

In this third edition, besides revisions to the second edition, new sections discussing Voronoi diagrams of line segments, farthest-point Voronoi diagrams, and realistic input models have been added.

The book focuses solely on theory, so it presents no real source code (only pseudo-code) which I think is good thing since that would otherwise have polluted the clarity of the explanations.

Many of the topics it covers has been a help to me as a programmer. Can be recommended for anyone interested in computation geometry - but it requires some computer science maturity so I don't recommend it unless you have a bachelor's degree in C.S. or something similar.

Jacob Marner, M.Sc.


The best computational geometry book!   May 5, 1999
11 out of 12 found this review helpful

I also completely disagree with the one-star review below. The "Dutch book" is the clearest, most complete, most up-to-date, best designed, best illustrated computational geometry textbook out there. Some of the material may be a bit advanced for undergraduates (and for those people I would recommend Joe O'Rourke's excellent "Computational Geometry in C"), but for graduate students and other researchers who want to learn computational geometry, this book is absolutely essential.

This is an algorithms textbook, though, not a textbook full of code. You will not find compilable code in the author's favorite programming language du jour -- this may be what the first reviewer meant by "desperately needed details". What you will find is clear, correct, well-motivated explanations of the underlying algorithms, data structures, and mathematics.

The book does have a few faults. The motivating examples are often forced ("mixing things" for convex hulls??). The authors deliberately chose to show only one algorithm for each problem they consider, and occasionally the algorithm they chose is not the simplest or most efficient. But these are minor points.

If you're going to buy just one computational geometry book, this is the one to get.


Lucid and Complete   June 19, 2001
Wayne Miller (The Woodlands, Texas United States)
6 out of 6 found this review helpful

Compared to other texts on Computational Geometry, like the Preparata / Shamos collection -- this book is simple to read; it's very well written.

I cannot understate the clarity of the book; if you try comparing this to other graduate texts on Computational Geometry -- this one blows them away.

I think it covers a broad range of topics and covers them well. It is a wealth of algorithms.


Makes for a great class   March 11, 2000
8 out of 9 found this review helpful

I taught a class using that book, and I found it an invaluable help as an instructor in presenting the material. Teaching layered range trees and fractional cascading for instance benefits immensely from the detailed pictures of the book. At times, I find the motivation part somewhat stretched, or limited, but always informative for the student, and giving a concrete, hands-on aspect to the topic. The algorithms are almost all practical -- and practiced! It's a book your students will keep on their shelf for a while even after the class is over. And the layout is clear. It certainly does not rule out other books (like the classic Preparata-Shamos, or O'Rourke's) because it does sometimes not cover problems covered in those books, but it adds a lot to them, so even if you have them, you might want to consider this one.


Buy this book immediately!!!   November 3, 1998
7 out of 9 found this review helpful

I completely disagree with the above commentor who evaluates it as a kind of bad book.

I can not find any errors in pseudo code, and it's very easy for me to understand and follow. It contains hundreds of figures which help students understand the concepts. The idea is so clear, and followed by good examples. It's also worth reading for all computer scientists and mathematicians who are working on geometry. I highly recommend to use it as a text for Graduate course.

It can be worth being the "BIBLE" of all computational geometers.