@techreport{KapoorSmid93,
TITLE = {New techniques for exact and approximate dynamic closest-point problems},
AUTHOR = {Kapoor, Sanjiv and Smid, Michiel},
LANGUAGE = {eng},
URL = {http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/93-159},
NUMBER = {MPI-I-93-159},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Saarbr{\"u}cken},
YEAR = {1993},
DATE = {1993},
ABSTRACT = {Let $S$ be a set of $n$ points in $\IR^{D}$. It is shown that a range tree can be used to find an $L_{\infty}$-nearest neighbor in $S$ of any query point, in $O((\log n)^{D-1} \log\log n)$ time. This data structure has size $O(n (\log n)^{D-1})$ and an amortized update time of $O((\log n)^{D-1} \log\log n)$. This result is used to solve the $(1+\epsilon)$-approximate $L_{2}$-nearest neighbor problem within the same bounds. In this problem, for any query point $p$, a point $q \in S$ is computed such that the euclidean distance between $p$ and $q$ is at most $(1+\epsilon)$ times the euclidean distance between $p$ and its true nearest neighbor. This is the first dynamic data structure for this problem having close to linear size and polylogarithmic query and update times.},
TYPE = {Research Report / Max-Planck-Institut für Informatik},
}