I am looking for data structures to answer nearest neighbor queries in 3D which are reasonably space efficient (ie use at most $O(n^{1+\epsilon})$ space) and fast ($O(n^{\epsilon})$ or $O(log^k(n))$ query time in the worst case).
As a summary of what I already know:
1D is trivial (just sort the points and use binary search).
2D is a bit trickier, but with a point location data structure + voronoi diagram you can do it in $O(n)$ space and $O(log(n))$ query time.
In 3D and above, that solution breaks down since the Voronoi diagram of a set of points is $O(n^{floor(d/2)})$.
I am aware of approximate techniques based on kd-trees or grid based methods, though these are dependent on assuming either a uniform distribution of points or something about the distance to the nearest neighbor, and don't perform so well in all cases. I am not interested in these randomized or approximate solutions - I want something that works for any data set in the worst case. Is there anything out there that does this, or is there some lower bound which blows this idea out of the water?
