5

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?

Josh Lee
  • 171,072
  • 38
  • 269
  • 275
Moeb
  • 10,527
  • 31
  • 84
  • 110

2 Answers2

4

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
  • 7,515
  • 1
  • 25
  • 41
  • 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. – Moeb Nov 11 '09 at 08:26
  • 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 Nov 11 '09 at 08:31
  • 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? – Moeb Nov 11 '09 at 08:40
  • 2
    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. – Hannes Ovrén Nov 11 '09 at 08:46
  • 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 Nov 11 '09 at 21:50
  • Selecting the median element rather than the middle of the input range would be better. Average is better than middle of input range, but not as good as median. Course if you use the median you'll either be sampling randomly, or sorting. If you sort, a binary search is probably better. – William Morrison Sep 09 '13 at 19:55
2

These two videos should help:

dgorissen
  • 6,207
  • 3
  • 43
  • 52