MPI-I-93-159
New techniques for exact and approximate dynamic closest-point problems
Kapoor, Sanjiv and Smid, Michiel
November 1993, 29 pages.
.
Status: available - back from printing
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.
New dynamic data structures are given that maintain a closest
pair of $S$. For $D \geq 3$, a structure of size $O(n)$ is
presented with amortized update time
$O((\log n)^{D-1} \log\log n)$. For $D=2$ and any non-negative
integer constant $k$, structures of size
$O(n \log n / (\log\log n)^{k})$ (resp.\ $O(n)$) are presented
having an amortized update time of
$O(\log n \log\log n)$ (resp.\
$O((\log n)^{2} / (\log\log n)^{k})$).
Previously, no deterministic linear size data structure having
polylogarithmic update time was known for this problem.
-
MPI-I-93-159.pdf
- Attachement: MPI-I-93-159.dvi.gz (47 KBytes); MPI-I-93-159.pdf (174 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1993-159
BibTeX
@TECHREPORT{KapoorSmid93,
AUTHOR = {Kapoor, Sanjiv and Smid, Michiel},
TITLE = {New techniques for exact and approximate dynamic closest-point problems},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-93-159},
MONTH = {November},
YEAR = {1993},
ISSN = {0946-011X},
}