The Road to the Closest Point is Paved by Good Neighbors

renewcommandReℝGiven a set P of n points in Red, and a parameter varepsilon ∈ (0,1), we present a new construction of a directed graph G, of size O(n/varepsilond), such that (1+varepsilon)-ANN queries can be answered by performing a greedy walk on G, repeatedly moving to a neighbor that is (significantly) better than the current point. To the best of our knowledge, this is the first construction of a linear size with no dependency on the spread of the point set. The resulting query time, is O( varepsilon-d log Psi), where Psi is the spread of P. The new construction is surprisingly simple and should be practical.