Our principal objective in this book is to describe some basic problems that arise in computer graphics and computational geometry and to present some practical and relatively simple methods for solving them. In these pages we will not attempt a comprehensive survey of these fields. Rather, we will cover a number of core problems and solutions that may serve as an introduction to these fields and at the same time prove both interesting and accessible to the reader.

Another goal of this book is to introduce the reader to the design and analysis of algorithms (an algorithm is a recipe or method for solving a computational problem). This will provide the framework for studying the algorithms we will cover. Themes discussed include elementary data structures such as lists and search trees, algorithmic paradigms such as divide and conquer, and methods for analyzing the performance of algorithms and data structures.

The problems we will cover are culled from the fields of computer graphics and computational geometry. Spurred on by pressures from the marketplace and by advances in computer technology (not least being the introduction of the personal computer), computer graphics has developed rapidly since its inception in the 1950s. By contrast, computational geometry is ancient, with roots in the straightedge-and-compass constructions of Euclid. Yet it too has undergone tremendous growth in the last several decades, encouraged by (and encouraging) advances in algorithmic science and by growing recognition of its wide applicability.