How does space partitioning algorithm for finding nearest neighbors work?

Question

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?

Answer 1

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

Answer 2

These two videos should help:

• Explaining how a KD tree is built up: http://www.youtube.com/watch?v=T9h2KKJ_Pl8
• Explaining how to perform nearest neighbour search: http://www.youtube.com/watch?v=2SbVSxWGtpI