Efficient data structure for location queries
Author
Hello,
In my settings there are points spread around a 2D plane. Now I want to get the closest of these points to my current location.
Which data structure and/or algorithm shows good performance for this operation? The implementation overhead should not be too high (if possible).
Regards,
You can give the kd-tree a try. It stores the points in a binary search tree. Look here to learn more about the neighbour-search-algorithm using a kd-tree.
Kimmi
Kimmi
A regular grid or spatial hash is about the simplest possible thing you could implement, and works quite well when objects are the same size (as they would be with points). The front page had a recent article that might help: http://www.gamedev.net/reference/snippets/features/spatialHash/
A hashed grid structure is actually rather difficult to use for NN queries, since it requires a uniform-cost traversal or similar circle-rasterization technique. As kimmi said, kd-trees are ideal for this. Additionally, there's plenty of preexisting kd-tree implementations out there to use.
The kd-tree structure has good worst case time performance, but its average case performance is about the same...O(log n). On the other hand, a regular grid has higher memory overhead, but can be tweaked to have average case lookup of nearly O(1) in practice, and is much easier to implement. Depending on your application, this may be significant. When I switched over from kd-tree to uniform grid for 3d spatial indexing of nearest neighbors within a radius, I experienced about a 100-fold speedup in my application.
You could store two binary search trees, one for each axis, which map positions on those axes to the points. Take the points to the left and right (in key order) of the sample point "current location" for both the x and y axes. So then you have up to 4 points, one of which is the closest. Return the one with the smallest distance. This approach is O(1), but I doubt it's particularly fast.
Quote:Original post by Baiame
You could store two binary search trees, one for each axis, which map positions on those axes to the points. Take the points to the left and right (in key order) of the sample point "current location" for both the x and y axes. So then you have up to 4 points, one of which is the closest.
That produces incorrect results. Consider the points the five preexisting points (-1,10),(1,10),(10,-1),(10,1), and (2,2), and consider the test point to be (0,0). Your method will return the first four points, when in fact the fifth is the closest.
Quote:This approach is O(1)Actually, it's O(log n).
Quote:Original post by Sneftel
That produces incorrect results. Consider the points the five preexisting points (-1,10),(1,10),(10,-1),(10,1), and (2,2), and consider the test point to be (0,0). Your method will return the first four points, when in fact the fifth is the closest.
Aha, right! I couldn't think of a counter-example, but it should've been obvious. The only meaningful information you can actually get out of that algorithm is a box which the real nearest neighbor is either within or on (EDIT- on second thought this is false). Guess you could use it to find potential NNs, though you've highlighted the fatal flaw: the number of worthless points you might get is unbounded.
Quote:Original post by Sneftel
Actually, it's O(log n).
Why? Finding the l/r elements (twice) is O(1), as is checking the distances, and determining the closest one. So the entire algorithm has to be O(1).
Quote:Original post by BaiameBecause a KD-Tree is still a binary tree, which requires log(n) steps down through the tree to reach the leaves.Quote:Original post by SneftelQuote:Original post by Sneftel
Actually, it's O(log n).
Why? Finding the l/r elements (twice) is O(1), as is checking the distances, and determining the closest one. So the entire algorithm has to be O(1).
[Edited by - iMalc on October 16, 2009 1:49:08 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
