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


Simple randomized algorithms for closest pair problems

Golin, Mordecai and Raman, Rajeev and Schwarz, Christian and Smid, Michiel

MPI-I-92-155. December 1992, 14 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
We present a conceptually simple, randomized incremental algorithm
for finding the closest pair in a set of $n$ points in
$D$-dimensional space, where $D \geq 2$ is a fixed constant.
Using dynamic perfect hashing, the algorithm runs in $O(n)$
expected time.
In addition to being quick on the average, this algorithm
is reliable: we show that it runs in $O(n \log n / \log\log n)$
time with high probability.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-92-155.pdfMPI-92-155.pdfMPI-I-92-155.dvi65 KBytes; 18488 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 = {Golin, Mordecai and Raman, Rajeev and Schwarz, Christian and Smid, Michiel},
  TITLE = {Simple randomized algorithms for closest pair problems},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-92-155},
  MONTH = {December},
  YEAR = {1992},
  ISSN = {0946-011X},