  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 $\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.
