# MPI-I-91-101

## 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

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.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 15201 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: **http://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},`

`}`