Preface

Summary

Computational geometry broadly construed is the study of algorithms for solving geometric problems on a computer. The emphasis in this text is on the design of such algorithms, with somewhat less attention paid to analysis of performance. I have in several cases carried out the design to the level of working C programs, which are discussed in detail.

There are many brands of geometry, and what has become known as “computational geometry,” covered in this book, is primarily discrete and combinatorial geometry. Thus polygons play a much larger role in this book than do regions with curved boundaries. Much of the work on continuous curves and surfaces falls under the rubrics of “geometric modeling” or “solid modeling,” a field with its own conferences and texts, distinct from computational geometry. Of course there is substantial overlap, and there is no fundamental reason for the fields to be partitioned this way; indeed they seem to be merging to some extent.

The field of computational geometry is a mere twenty years old as of this writing, if one takes M. I. Shamos's thesis (Shamos 1978) as its inception. Now there are annual conferences, journals, texts, and a thriving community of researchers with common interests.

Topics Covered

I consider the “core” concerns of computational geometry to be polygon partitioning (including triangulation), convex hulls, Voronoi diagrams, arrangements of lines, geometric searching, and motion planning. These topics from the chapters of this book. The field is not so settled that this list can be considered a consensus; other researchers would define the core differently.