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.