Nearest neighbor search through function minimization.
Chang Shu, Michael Greenspan, Guy Godin · 2001
This paper describes a solution to the nearest neighbor problem. The proposed algorithm, which makes use of the triangle inequality property, is considered from a function minimization perspective. The distance function is regularized through the computation of distance to a reference point; an initial starting point is rapidly found, and used in an iterative renement using search over a sorted list. The algorithm is described, and simulation results are provided that suggest better performance than that obtained with spatial partition techniques such as Elias and k-d tree, for moderate size point sets. 1