This paper considers the expected number of hyperrectangles corresponding to leaf nodes which will provably need to be searched. Such hyperrectangles intersect the volume enclosed by a hypersphere centered on the query point whose surface passes through the nearest neighbour. For example, in Figure 6.5 the hypersphere (in this 6-9 Figure 6.5 Generally during a nearest neighbour search only a few leaf nodes need to be inspected.


CiteSeerX — An Intoductory Tutorial on Kd-Trees

Links and resources

BibTeX key:
search on:

Comments and Reviews  

There is no review or comment yet. You can write one!


Cite this publication