Computational Geometry

Computational geometry is the algorithmic study of geometric problems and objects. Compared to the other topics in this book, computational geometry emerged as a field quite recently, with Shamos's Ph.D. thesis [Sha78] typically cited as its founding event. Its emergence coincided with the explosion of computer graphics and windowing systems, which directly or indirectly provide much of the motivation for geometric computing. The past twenty years have seen enormous growth in computational geometry, resulting in a significant body of useful algorithms, software, textbooks, and research results.  

Good books on computational geometry include:

• Preparata and Shamos [PS85] - Although aging a bit, this book remains the best general introduction to computational geometry, stressing algorithms for convex hulls, Voronoi diagrams, and intersection detection.
• O'Rourke [O'R94] - Perhaps the best practical introduction to computational geometry. The emphasis is on careful and correct implementation (in C language) of the fundamental algorithms of computational geometry. These implementations are available from http://grendel.csc.smith.edu/ orourke/.
• Edelsbrunner [Ede87] - This is the definitive book on arrangements, a topic that runs through most of computational geometry. Although not appropriate for beginners, it provides an important perspective for advanced geometers.
• Mulmuley [Mul94] - An approach to computational geometry through randomized incremental algorithms. Very interesting, but likely too narrow to serve as a general introduction.
• Nievergelt and Hindrichs [NH93] - This idiosyncratic algorithms text focuses on problems in graphics and geometry. Good coverage of line drawing, intersection algorithms, and spatial data structures, but with too many topics touched on too lightly to serve as an effective reference.

The leading conference in computational geometry is the ACM Symposium on Computational Geometry, held annually in late May or early June. Although the primary results presented at the conference are theoretical, there has been a concerted effort on the part of the research community to increase the presence of applied, experimental work through video reviews and poster sessions. The other major annual conference is the Canadian Conference on Computational Geometry (CCCG), typically held in early August. Useful literature surveys include [Yao90].

A unique source of computational geometry information is geom.bib, a community effort to maintain a complete bibliography on computational geometry. It references over eight thousand books, papers, and reports and includes detailed abstracts for many of them. Grep-ing through the geom.bib is an amazingly efficient way to find out about previous work without leaving your office. It is available via anonymous ftp from ftp.cs.usask.ca, in the file pub/geometry/geombib.tar.Z.  

There is a growing body of implementations of geometric algorithms. We point out specific implementations where applicable in the catalog, but the reader should be aware of three specific WWW sites:

• The Geometry Center's directory of computational geometry software, maintained by Nina Amenta, is the ``official'' site for all computational geometry software. Check here first to see what is available: http://www.geom.umn.edu/software/cglist/.
• Graphics Gems is a series of books dedicated to collecting small codes of interest in computer graphics. Many of these programs are geometric in nature. All associated codes are available from ftp://ftp-graphics.stanford.edu/pub/Graphics/GraphicsGems.  
• CGAL (Computational Geometry Algorithms Library) is a joint European project now underway to produce a comprehensive library of geometric algorithms. This will likely become the definitive geometric software project. Check out its progress at http://www.cs.ruu.nl/CGAL/.  

• Robust Geometric Primitives
• Convex Hull
• Triangulation
• Voronoi Diagrams
• Nearest Neighbor Search
• Range Search
• Point Location
• Intersection Detection
• Bin Packing
• Medial-Axis Transformation
• Polygon Partitioning
• Simplifying Polygons
• Shape Similarity
• Motion Planning
• Maintaining Line Arrangements
• Minkowski Sum