Abstract

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.

Description

CiteSeerX — An Intoductory Tutorial on Kd-Trees

Links and resources

URL:
BibTeX key:
Moore91anintoductory
search on:

Comments and Reviews  
(0)

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

Tags


Cite this publication