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?

Something like a K-dimension or a P-R-Quad Tree? I like K-D trees
because they are just binary trees with a fancy insert and delete.The
basic idea if that the depth from the root of the tree determines which
of the dimension you organize that level by. Compare by X at root, Y at
the next depth, Z next, then back to X and so on.

Searching also gives you the option of radius searches, so you can get
all key/values withing Q distance of X,Y,Z.

An R-Tree might also do what you want, but I haven't programed one.

Post a reply to this message