A True $O(n\log n)$ Algorithm for the All-k-Nearest-Neighbors Problem

In this paper we examined an algorithm for the All-k-Nearest-Neighbor problem proposed in 1980s, which was claimed to have an $O(n\log n)$ upper bound on the running time. We find the algorithm actually exceeds the so claimed upper bound, and prove that it has an $\mathrm{\Omega }(n^2)$ lower bound on the time complexity. Besides, we propose a new algorithm that truly achieves the $O(n\log n)$ bound. Detailed and rigorous theoretical proofs are provided to show the proposed algorithm runs exactly in $$O(n\log n)$$ time.