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 fields, 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.
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...
