Algorithms in a Nutshell

Range Queries | 293

Computational

Geometry

Input/Output

Input

A set ofnpointsPind-dimensional space and ad-dimensional hypercube that

specifies the desired range query.

Output

The full set of points enclosed by the range query. The points do not appear in

any specific order.

Assumptions

The range queries are aligned properly with the axes in thed-dimensional data set

since they are specified byd individual ranges, for each dimension of the input set.

Context

Because kd-trees become unwieldy for a large number of dimensions, this algo-

rithm and overall approach is likely to degrade accordingly.

Forces

Because of the versatility of kd-trees, this approach is likely to afford other effi-

cient algorithms. Note that both NEARESTNEIGHBORand RANGEQUERY

problems operate more efficiently because of the kd-trees.

Solution

The Java solution shown in Example 9-6 is a method of theDimensionalNodeclass,

which is simply delegated by thesearch(IHypercube)method found inKDTree. The

key efficiency gain of this algorithm occurs when the region for aDimensionalNode

is wholly contained within the desired range query. In this circumstance, all

descendant nodes of theDimensionalNodecan be added to the results collection

because of the kd-tree property that the children for a node are wholly contained

within the region of any of its ancestor nodes.

Example 9-6. Range Query implementation

public void search (IHypercube space, ArrayList<IMultiPoint> results) {

// Wholly contained? Take all descendant points

if (space.contains (region)) {

this.drain(results);

return;

}

// Is our point at least contained?

if (space.intersects (cached)) {

results.add(point);

}

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