Title  $L_{\infty}$-Nearest Neighbor Search in High Dimensions.  

Authors  Helmut Alt and Laura Heinrich-Litan.  

Published  In Proceedings of the 17th ACM Symposium on Computational Geometry, Boston, June 2001.  
Abstract  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.  

Downloading  [ps] [pdf]