Algorithms in a Nutshell

Chapter 9. Computational Geometry

Overview

This overview introduces a set of problems from the field of computational geometry. Many of these problems were first investigated by mathematicians over the past few centuries. Since the 1970s, computational geometry has been recognized as the systematic study of geometric algorithms and data structures that enable their efficient execution. These algorithms solve numerous real-world problems, some of which we will present in this chapter. Too often, the data structures and algorithms presented in this chapter have been considered "too advanced" for the undergraduate curriculum. Software professionals, however, will readily be able to learn these structures and the principles behind the algorithms and apply them to the challenging problems they must face.

Classifying Problems

A computational geometry problem inherently involves geometric objects, such as points, lines, and polygons. More precisely, a computational geometry problem is defined by (a) the type of input data to be processed, (b) the computation to be performed, and (c) whether the task is static or dynamic. These classifications help identify the techniques that can improve efficiency across families of related problems.

Input data

A computational geometry problem must define the input data. The following are the most common types of input data to be processed:

• A set of points in the two-dimensional plane

• A set of line segments in the plane

• A set of rectangles in the plane

• A set ...