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

Hengzhao Ma, Jianzhong Li

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…