Algorithms in a Nutshell

Nearest Neighbor Queries

Given a set of points P in a two-dimensional Cartesian plane, answer nearest neighbor queries of the form, "What point in P is closest to point x?" Note that x does not have to be a preexisting point in P. These queries also extend to input sets whose points are found in n-dimensional space. The naïve implementation is to inspect all points in P, resulting in a linear O(n) algorithm. Since P is known in advance, perhaps there is some way to structure its information to speed up queries by discarding from consideration large groups of points in P.

Perhaps we could partition the plane into k² bins of some fixed size m by m, as shown in Figure 9-18(a). Here 10 input points in P (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 point x (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 inefficiencies 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, partitioning P into fixed bins is ...