Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


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

Smid, Michiel

MPI-I-91-101. March 1991, 28 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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

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.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-91-101.pdf15201 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
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},