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?


2 Answers 2


I like Drost's hierarchical voxel hashing. It has an average time complexity of $O(log(log(|D|)))$, where $|D|$ is the number of points in data cloud. While the construction is a bit more tedious, searching gets much faster.

The method is also extended to a journal version, found under this link.


Exact nearest neighbour queries in kd trees are perfectly feasible. Bentley's original paper gave an algorithm, but the better algorithm was in the follow-up paper. This is the tech report version:

Friedman, Bentley, and Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time, SLAC-PUB-1549, July 1976.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.