Computational Geometry

The standard textbook is by Preparata and Shamos. This is very well written but it assumes that the reader has already taken a standard algorithms course and can fill in non-trivial implementation details. It is also getting a bit old (1985).

More recently, O'Rourke and Laszlo have produced textbooks which assume less background than Preparata and Shamos. (Despite its title, the Laszlo book seems to be almost entirely computational geometry.) The textbook by Mulmuley is at about the same level as Preparata and Shamos, but covers randomized algorithms as well as deterministic ones.

The book by de Berg and company is extremely new and does not yet have a track record. It looks extremely good: coverage similar to Preparata and Shamos, but easier to read and more up to date.

• Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf (1997) Computational Geometry, Springer-Verlag, Berlin.
• Laszlo, Michael J. (1996) Computational Geometry and Computer Graphics in C++, Prentice-Hall, Upper Saddle River, NJ.
• O'Rourke, Joseph (1993) Computational Geometry in C, Cambridge University Press, Cambridge, UK.
• Preparata, F. P. and M. I. Shamos (1985) Computational Geometry: An Introduction, Spinger-Verlag, New York.
• Mulmuley, Ketan (1994) Computational Geometry: An Introduction through Randomized Algorithms, Prentice-Hall, Englewood Cliffs NJ (ISBN: 0-13-336363-5).

A wide variety of algorithms use techniques based on Voronoi diagrams: When they can be applied, these methods are very efficient. The basics of these methods are described in the texts by O'Rourke and Preparata and Shamos, listed above. There is also a comprehensive, though somewhat expensive ($130) book by Okabe, Boots, and Sugihara.

• Atsuyuki Okabe, Barry Boots, Kokichi Sugihara (1992) Spatial tessellations : concepts and applications of Voronoi diagrams, John Wiley & Sons, New York.

Handbook Main Page

Ownership, Maintenance, and Disclaimers

Last modified