Algorithms in a Nutshell

Nearest Neighbor Queries | 281

Computational

Geometry

Perhaps we could partition the plane intok^2 bins of some fixed sizembym,as

shown in Figure 9-18(a). Here 10 input points inP(shown as circles) are placed

into nine enclosing bins (the large shaded number reflects the number of points in

the respective bin). When searching for the closest neighbor for a pointx(shown

as a small black square), find its enclosing bin. If that bin is not empty, then we

only need to search the bins that intersect the focus circle whose radius is

In this example, however, there are no points in the target bin, and the three

neighboring bins will need to be examined. This approach may lead to gross inef-

ficiencies because (a) most of the bins may in fact be empty, and (b) the algorithm

would still have to search multiple neighboring bins. In brief, partitioningPinto

fixed bins is ineffective for resolving nearest neighbor queries.

An alternate solution is to construct the Voronoi diagram (Preparata and Shamos,

1985) of the setP, which partitions the plane into a set ofnregionsRi(0≤i<n), each

of which is defined as “the set of points closer topithan to any other point inP.”

Thus the regions self-adapt to be as large as required.*In a two-dimensional plane,

each region is a polygon (for higher dimensions, each region is ann-dimensional

polyhedron). The image in Figure 9-18(b) shows the Voronoi diagram for the

same points used earlier in Figure 9-18(a). Once the structure is computed, the

result of a nearest neighbor query is immediate once the enclosing regionRiis

found. The algorithm for constructing Voronoi diagrams takes O(nlogn)inthe

average case, but it is complicated to implement. With a Voronoi diagram, nearest

neighbor queries can be answered in O(logn).

In Figure 9-19(a), the same 10 points from Figure 9-18 are shown in a kd-tree, so

named because it can subdivide ak-dimensional plane along the perpendicular axes

of the coordinate system. The structure of the kd-tree from Figure 9-19(a) is depicted

as a binary tree in Figure 9-19(b). For the remainder of this discussion we assume

a two-dimensional tree, but the approach can be used for arbitrary dimensions.

* Note that in the Voronoi diagram, points on the convex hull have “open-ended” regions that ex-

tend outward to the edge of the diagram, whereas internal nodes have finite regions.

Figure 9-18. Bin and Voronoi approaches toward nearest neighbor

2 m

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