Finding k nearest neighbors for all points

If you have n points in 2d space, how quickly can you report the k nearest points to every point under Euclidean distance? If it helps speed things up we can ignore points that are more than some distance away as well so potentially return fewer than k. A randomized or approximate solution would also be interesting.

One solution is to build a kd tree and do an independent look up for every point. Is this as good as it gets?

$O(kn+n\log n)$. See

P.B. Callahan, S.R. Kosaraju, A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential ﬁelds, J. ACM 42 (1995) 67–90.

In some models of computation the $O(n\log n)$ part can be reduced or removed; see also

T. M. Chan, Well-separated pair decomposition in linear time?, Inf. Proc. Lett. 2008.

• Thank you. As I would like to implement a solution, do you have a feeling for which of the existing methods is practical? Searching using your answer gives quite a few options.
– Simd
Jul 18, 2013 at 21:06

In Handbook of discrete and computational geometry (Goodman and Rourke eds.), there is a chapter on the complexity of knn search. I do not remember the complexities discussed there, for the high dimensional cases, but they are effectively not "miraculous".

The subset sum problem can be converted quite easily to a knn search on lp norms, this may hint at why there seems to be a research problematic.

You can use the fundamental theorem of arithmetic to map d-dimensional point to the line and then use a variant of binary search for intervals... And do some additional work...

• I think single point knn queries and all points knn are subtly different.
– Simd
Jul 25, 2013 at 5:44
• Single point knn when the query is the 0-vector is equivalent to searching a list of norms. Now if you have N possible queries, you can normalize your data to the N queries each of which are now the new origin of the system. This yields an N-dimensional list of numbers, like a distance matrix... If N tends to infinity, you get a manifold...
– Phil
Jul 25, 2013 at 13:11