S. Arya and D. Mount introduce the following notion for approximating
the nearest neighbor in *k*-d trees [2]: Given an
, then the point
is the
-approximate
nearest neighbor of the point
, iff

where denotes the true nearest neighbor, i.e., has a maximal distance of to the true nearest neighbor. Using this notation, in every step the algorithm records the closest point . The search terminates if the distance to the unanalyzed leaves is larger than

root 2007-05-31