MPI-INF/SWS Research Reports 1991-2021
2. Number - All Departments
MPI-I-91-123
An optimal algorithm for the on-line closest-pair problem
Schwarz, Christian and Smid, Michiel and Snoeyink, Jack
November 1991, 11 pages.
.Status: available - back from printing
We give an algorithm that computes the closest pair in a set
of $n$ points in $k$-dimensional space on-line, in $O(n \log n)$
ime. The algorithm only uses algebraic functions and, therefore,
is optimal. The algorithm maintains a hierarchical subdivision of $k$-space
into hyperrectangles, which is stored in a binary
tree. Centroids are used to maintain a balanced decomposition
of this tree.
-
MPI-I-91-123.pdf
- Attachement: MPI-I-91-123.pdf (12141 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1991-123
BibTeX@TECHREPORT{SchwarzSmidSnoeyink91,
AUTHOR = {Schwarz, Christian and Smid, Michiel and Snoeyink, Jack},
TITLE = {An optimal algorithm for the on-line 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-123},
MONTH = {November},
YEAR = {1991},
ISSN = {0946-011X},
}