Exact L ∞ nearest neighbor search in high dimensions
Helmut Alt, Laura Heinrich-Litan · 2001
We present an algorithm for solving the nearest neighbor problem with respect to $L_{\infty}$-distance. It requires no preprocessing and storage only for the point set $P$. Its average runtime assuming that the set $P$ of $n$ points is drawn randomly from the unit cube $[0,1]^{d}$ under uniform distribution is essentially $\Theta (nd/ln\; n)$ thereby improving the brute-force method by a factor of $\Theta (1/ln\; n)$. Several generalizations of the method are also presented, in particular to other “well-behaved” probability distributions and to the important problem of finding the $k$ nearest neighbors to a query point.