非表示:
キーワード:
-
要旨:
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.
