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

$$\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

$$\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.