English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

New techniques for exact and approximate dynamic closest-point problems

MPS-Authors
/persons/resource/persons44728

Kapoor,  Sanjiv
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45509

Smid,  Michiel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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.