kd-tree stores points in inner nodes? If yes, how to search for NN? 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?
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) &lt;= node's cut-value )
        NN(left-child)
        if( cut-coor(q) + current best distance &gt; node's cut-value )
            NN(right-child)
        end if
    else {cut-coor(q) &gt; node's cut value}
        NN(right-child)
        if(cut-coor(q) - current best distance &lt;= 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.