Algorithms in a Nutshell

Overview | 255

Computational

Geometry

In the sections of this chapter, we present the various computational abstractions

used to solve computational geometry problems. These techniques are by no

means limited to geometry problems and have many real-world applications. For

example, the sweep technique shows how to organize objects into a complete

ordering for processing when those objects (such as points, line segments, or poly-

gons) have no immediate ordering available.

Nature of the task

A static task requires only that an answer be delivered on demand for a specific

input data set. However, there are two important dynamic considerations that

alter the way that a problem may be approached:

• Is the task to be requested multiple times over the same input data set? If so,
  then one should preprocess the input set to improve the efficiency of future
  task requests.


• Might the input data set change after the task has been requested? If so, then
  one should investigate data structures that gracefully enable such alterations.
  Dynamic tasks require data structures that can grow and shrink as demanded by
  changes to the input set. Arrays of fixed length might be suitable for static tasks,
  but dynamic tasks require one to assemble linked lists or stacks of information
  together to serve a common purpose. Refer to Chapter 6 for the benefits and limi-
  tations of the two ways to store graphs, namely adjacency lists and adjacency
  matrices.

Assumptions

The most effective approach to develop or understand an efficient solution to a

problem is to analyze the assumptions and invariants about the input set (or the

task to be performed). For example:

Table 9-1. Computational geometry problems and their application

Computational geometry problem(s) Real-world application(s)

Find the closest point to a given point. Find the furthest

point from a given point.

Given a car’s location, find the closest gasoline station.

Given an ambulance station, find the furthest hospital

from a given set of facilities to determine worst-case

travel time.

Determine whether a polygon is simple (i.e., two non-

consecutive edges cannot share a point).

An animal from an endangered species has been tagged

with a radio transmitter that emits the animal’s location.

Scientists would like to know when the animal crosses its

own path to find commonly used trails.

Compute the smallest circle enclosing a set of points.

Compute the largest interior circle of a set of points that

doesn’t contain a point.

Statisticians use various techniques when analyzing data.

Enclosing circles can identify clusters, whereas large gaps

in data suggest anomalous or missing data.

Determine the full set of intersections within a set of line

segments, or within a set of circles, rectangles, or arbi-

trary polygons.

Very Large Scale Integration (VLSI) design rule checking.

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