Algorithms in a Nutshell

251

Chapter 9. Computational Geometry..........................................................................................................................................

9

Computational Geometry

Overview

This overview introduces a set of problems from the field of computational geom-

etry. 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 of arbitrary polygons in the plane

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use