Algorithms in a Nutshell

Nearest Neighbor Queries | 287

Computational

Geometry

The key to understanding NEARESTNEIGHBORis that we first locate the region

where the target point would have been inserted, since this will likely contain the

closest point. We then validate this assumption by recursively checking from the

root back down to this region to see whether some other point is actually closer

(this could easily happen because the rectangular regions of the kd-tree were

created based upon the arbitrary input set). In unbalanced kd-trees, this checking

process might incur an O(n) total cost, reinforcing the notion that the input set

must be properly processed.

The example solution has two improvements to speed up its performance. First,

the comparisons are made on the “raw”double[]array representing each point.

Second, ashortermethod inDimensionalNodeis used to determine when the

distance between twod-dimensional points is smaller than the minimum distance

result = point;

}

// determine if we must dive into the subtrees by computing direct

// perpendicular distance to the axis along which node separates

// the plane. If d is smaller than the current smallest distance,

// we could "bleed" over the plane so we must check both.

double dp = Math.abs(coord - rawTarget[dimension-1]);

IMultiPoint newResult = null;

if (dp < min[0]) {

// must dive into both. Return closest one.

if (above != null) {

newResult = above.nearest (rawTarget, min);

if (newResult != null) { result = newResult; }

}

if (below != null) {

newResult = below.nearest(rawTarget, min);

if (newResult != null) { result = newResult; }

}

} else {

// only need to go in one! Determine which one now.

if (rawTarget[dimension-1] < coord) {

if (below != null) {

newResult = below.nearest (rawTarget, min);

}

} else {

if (above != null) {

newResult = above.nearest (rawTarget, min);

}

}

// Use smaller result, if found.

if (newResult != null) { return newResult; }

}

return result;

}

Example 9-5. Nearest Neighbor Queries implemented with kd-tree (continued)

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