k-D Tree Nearest Neighbor Search

Yesterday I posted a simple demonstration of the kD tree data structure, today I am posting an animation of the nearest neighbor search algorithm for it. The tree itself should be very straightforward for any one familiar with trees; the nearest neighbor search is where things get a little tricky. I looked up the nearest neighbor algorithm on Wikipedia and was not entirely clear how it worked. I suspect that most people would not understand the description there unless they already understood the algorithm, which is probably why you are here. So, I created an animation that hopefully makes things easier to understand.

The first step is to locate the location where the point would be located if it were added to the tree. As the tree is traversed the distance between the point and the current node should be recorded. Next, you have to go back up the tree evaluating each branch of the tree that could have points within the current minimum distance. Check out the animation below to get a better idea of how it works.

Comments (newest first)