Question

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?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top