Cover by Gary Pollice, Stanley Selkow, George T. Heineman

Safari, the world’s most comprehensive technology and business learning platform.

Find the exact information you need to solve a problem on the fly, or go deeper to master the technologies and skills you need to succeed

Start Free Trial

No credit card required

O'Reilly logo

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 k2 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

image with no caption

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 ...

Find the exact information you need to solve a problem on the fly, or go deeper to master the technologies and skills you need to succeed

Start Free Trial

No credit card required