On Finding K Nearest Neighbors in the Plane.

摘要

The nearest neighbor problem arises in several applications such as density estimation, pattern classification and information retrieval. The problem is to find, among a set of points (or feature vectors), the one which is most similar or closest to a given test point according to some dissimilarity or distance measure. One straightforward way of solving it is to compute the 'distances' between each point of the set and the test point and then search for the point P with minimum distance. The k-nearest neighbor problem to be considered here is a variant of the classical nearest neighbor problem.