For finding the nearest neighbor, Space Partitioning is one of the algorithms. How does it work?
Suppose I have a 2D set of points (x and y coordinates), and I am given a point (a,b). How would this algorithm find out the nearest neighbor?
views:
308answers:
1
+4
A:
Spacial partitioning is actually a family of closely related algorithms that partition space so that applications can process the points or polygons easier.
I reckon there are many ways to solve your problem. I don't know how complex you are willing to build your solution. A simple way would probably to build a binary tree cutting the space into 2. All the points divided between some middle plane. Build your tree by subdividing recursively until you run out of points.
Searching for the nearest neighbor will then be optimized, because each traversal of the tree narrows down the search area.
In some literature, they call this a kd tree
Andrew Keith
2009-11-11 08:18:52
suppose I have points `(0,0), (1,2),(1,0),(-1,0)` and the point given is `(2,2)`. How would the algorithm work then? I read about it but I am not sure how the partitioning and tree traversal will be done. It would be helpful if oyu could explain what you mentioned on this small example. Thanks.
Amoeba
2009-11-11 08:26:10
Calculate the range of X and Y. In this case, X ranges from -1 to 2, Y from 0 - 2. The root of the tree is the middle, probably (1.5,1). Separate all the points into groups split by the root. Then perform the same for each group splitting them even more. the leaves of the tree will be individual points. You can then find the closes point by traversing the tree checking each node versus your point until you find the closest.
Andrew Keith
2009-11-11 08:31:40
but in that case, you will have to compare `(2,2)` against every other node and it will run in linear time. So, what will be the use of the tree then?
Amoeba
2009-11-11 08:40:39
You will try every node on the path, not every node in the tree. Thus your search space is pruned and very much smaller than testing against all points. My guess is that it will run in logarithmic time (since you will only try one node per depth) instead of linear.
kigurai
2009-11-11 08:46:16
Correct. When traversing the tree, you can safely ignore branches of a node which are not in your search area. In this example , because there are only 5 points, its not so useful. In 3d applications with millions of vertices, tree's like these are essential in processing the scene
Andrew Keith
2009-11-11 21:50:52