# Item

ITEM ACTIONSEXPORT

Released

Report

#### New techniques for exact and approximate dynamic closest-point problems

##### External Ressource

No external resources are shared

##### Fulltext (public)

MPI-I-93-159.pdf

(Any fulltext), 174KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Kapoor, S., & Smid, M.(1993). *New techniques for exact
and approximate dynamic closest-point problems* (MPI-I-93-159). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B42E-2

##### 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.