MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


Dynamic rectangular point location, with an application to the closest pair problem

Smid, Michiel

March 1991, 28 pages.

Status: available - back from printing

In the $k$-dimensional rectangular point location problem, we have to store a set of $n$ non-overlapping axes-parallel hyperrectangles in a data structure, such that the following operations can be performed efficiently: point location queries, insertions and deletions of hyperrectangles, and splitting and merging of hyperrectangles. A linear size data structure is given for this problem, allowing queries to be solved in $O((\log n)^{k-1} \log\log n )$ time, and allowing the four update operations to be performed in $O((\log n)^{2} \log\log n)$ amortized time. If only queries, insertions and split operations have to be supported, the $\log\log n$ factors disappear. The data structure is based on the skewer tree of Edelsbrunner, Haring and Hilbert and uses dynamic fractional cascading. This result is used to obtain a linear size data structure that maintains the closest pair in a set of $n$ points in $k$-dimensional space, when points are inserted. This structure has an $O((\log n)^{k-1})$ amortized insertion time. This leads to an on-line algorithm for computing the closest pair in a point set in $O( n (\log n)^{k-1})$ time.

  • MPI-I-91-101.pdf
  • Attachement: MPI-I-91-101.pdf (15201 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Smid, Michiel},
  TITLE = {Dynamic rectangular point location, with an application to the closest pair problem},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-91-101},
  MONTH = {March},
  YEAR = {1991},
  ISSN = {0946-011X},