Finding k nearest neighbors for all points
$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.