Hi guys.

I'm guessing somebody here is likely to know the answer to this one...

I want a data structure that stores key/value pairs where the keys are 
points in 3D space. In particular, I want to be able to *efficiently* 
look up the N points nearest to any given location. (Hopefully it's also 
fairly quick to add new points to the structure.)

The points don't have any particular arrangement. (They're certainly not 
a regular grid - in that case, lookup would be quite simple.)

One algorithm I could use is to store a list of key/value pairs, and 
sort the list by the distance between each key and the target point, 
then read off the first few values in the list. This *works*, but it's 
absurdly inefficient. (It's O(n log n) in the total number of entries.) 
Does anybody know of something a little faster?

Post a reply to this message