next up previous
Next: Approximate box decomposition trees Up: Closest Point Search Previous: The optimized k-d tree

Approximate k-d tree search

S. Arya and D. Mount introduce the following notion for approximating the nearest neighbor in k-d trees [2]: Given an $ {\varepsilon }>
0$, then the point $ \mathbf{p} \in D$ is the $ (1 + {\varepsilon })$-approximate nearest neighbor of the point $ \mathbf{p}_q$, iff

$\displaystyle \left\lvert\left\lvert \mathbf{p} - \mathbf{p}_q \right\rvert\rig...
...) \left\lvert\left\lvert \mathbf{p}^* - \mathbf{p}_q \right\rvert\right\rvert ,$    

where $ \mathbf{p}^*$ denotes the true nearest neighbor, i.e., $ \mathbf{p}$ has a maximal distance of $ {\varepsilon }$ to the true nearest neighbor. Using this notation, in every step the algorithm records the closest point $ \mathbf{p}$. The search terminates if the distance to the unanalyzed leaves is larger than

$\displaystyle \left\lvert\left\lvert \mathbf{p}_q - \mathbf{p} \right\rvert\right\rvert /(1+{\varepsilon }).

Fig. 3 (left) shows an example where the gray cell needs not to be analyzed, since the point $ \mathbf{p}$ satisfies the approximation criterion.

root 2007-05-31