[Solved]: kd-tree stores points in inner nodes? If yes, how to search for NN?

Problem Detail: 

The link in wikipedia about kd-trees store points in the inner nodes. I have to perform NN queries and I think (newbie here), I am understanding the concept.

However, I was said to study Kd-trees from Computational Geometry Algorithms and Applications (De Berg, Cheong, Van Kreveld and Overmars), section 5.2, page 99. The main difference I can see is that Overmars places the splitting data in the inner nodes and the actual points of the dataset in the leaves. For example, in 2D, an inner node will hold the splitting line.

Wikipedia on the other hand, seems to store points in inner nodes and leaves (while Overmars only on leaves).

In this case, how do we perform nearest neighbour search? Moreover, why there is this difference?

Asked By : gsamaras

Answered By : gsamaras

Without storing points in the inner nodes, but the cut value and cut coordinate, one can use this algorithm to perform NN search:

Procedure NN(node), given query q   if(node is leaf)     Search all points, in node, update current best   else {internal node}     if( cut_coord(q) <= node's cut-value )         NN(left-child)         if( cut-coor(q) + current best distance > node's cut-value )             NN(right-child)         end if     else {cut-coor(q) > node's cut value}         NN(right-child)         if(cut-coor(q) - current best distance <= node's cut-value)             NN(left-child)         end if     end if(left/right)   end if(node) 

In order to perform ANN search, see the answer here.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23636

 Ask a Question

 Download Related Notes/Documents