MPI-I-91-101
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.
-
- Attachement: MPI-I-91-101.pdf (15201 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1991-101
BibTeX
@TECHREPORT{Smid91a,
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},
}