MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


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.pdfMPI-I-93-159.pdfMPI-I-93-159.dvi.gz
  • Attachement: MPI-I-93-159.dvi.gz (47 KBytes); MPI-I-93-159.pdf (174 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  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},