Cover by Gary Pollice, Stanley Selkow, George T. Heineman

Safari, the world’s most comprehensive technology and business learning platform.

Find the exact information you need to solve a problem on the fly, or go deeper to master the technologies and skills you need to succeed

Start Free Trial

No credit card required

O'Reilly logo

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 ...

Find the exact information you need to solve a problem on the fly, or go deeper to master the technologies and skills you need to succeed

Start Free Trial

No credit card required