Orchid XP v7 wrote:
> 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?

If you want speed after the points are all read in, then build an MxN 
array of indices to the list (M is the total number of points, N is the 
number of desired neighbors).  It's an O(M^2 * N) problem to build that 
structure (although that can probably be reduced), but once the 
structure is built, you get the maximum speed.

Regards,
John

Post a reply to this message