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)$
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.pdf||65 KBytes; 18488 KBytes|
|Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView|