The Road to the Closest Point is Paved by Good Neighbors

Given a set \(\mathsf{P}\) of \(n\) points in \(\mathbb{R}^d\), and a parameter \(\varepsilon \in (0,1)\), we present a new construction of a directed graph \(\mathsf{G}\), of size \(O(n/\varepsilon^d)\), such that \((1 + \varepsilon)-\mathsf{ANN}\) queries can be answered by performing a greedy walk on \(\mathsf{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 \(\mathsf{P}\). The new construction is surprisingly simple and should be practical.