Algorithms in a Nutshell

Overview | 259

Computational

Geometry

Answering nearest neighbor queries

Given a set of pointsPin a two-dimensional plane, answer nearest neighbor

queries of the form, “What point inPis closest to pointxusing Euclidean

distance?” Note that pointx does not have to already exist inP.

Given query pointx, compare its distance to all other points inPto find the

closest one. This requires O(n) linear steps. As we saw in Chapter 5, binary trees

helped to reduce the search by eliminating from consideration groups of points

that could not be part of the solution. We use trees to partition the points in the

two-dimensional plane to reduce the search time as well. The extra cost of prepro-

cessing all points inPinto an efficient structure is recouped later by savings of the

query computations, which becomes O(logn). If the number of searches is going

to be small, then perhaps the obvious O(n) comparison is best.

Answering range queries

Instead of searching for a specific target point, a query could instead request all

points found within a given rectangular region of the two-dimensional plane. The

obvious solution requires one to determine whether the target rectangular region

contains each point in the set, resulting in O(n) performance.

The same data structure developed for nearest-neighbor queries also supports

these queries, known as “orthogonal range” because the rectangular query region

is aligned with thexandyaxes of the plane. The only way to produce better than

O(n) performance is to find a way to both (a) discard from consideration a group

of points, and (b) include in the query result a group of points. Using a kd-tree,

the query is performed using a recursive traversal, and the performance can be

wherer is the number of points reported by the query.

Summary

The code solutions we present for these problems will conform to the API defini-

tions shown in Table 9-2. For each problem, this table also summarizes the

performance of the algorithms discussed in this chapter.

Table 9-2. API definition of problems discussed in this chapter

Problem API description

Convex Hull public interface IConvexHull {

/** Compute ordered array of hull points. */

IPoint[] compute (IPoint[] points);

}

Obvious solution: O(n^4 )

Average-case CONVEXHULLSCAN: O(n logn)

Intersecting Line Segments public abstract class IntersectionDetection {

/** Determine all intersections. */

public abstract Hashtable<IPoint,ILineSegment[]>

intersections (ILineSegment[] segments);

}

Obvious solution: O(n^2 )

Average-case LINESWEEP: O((n+k) logn) withk=number of intersections found

O()nr+

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