hide
Free keywords:
-
Abstract:
Let $S$ be a set of $n$ points in $D$-dimensional space, where
$D$ is a constant,
and let $k$ be an integer between $1$ and $n \choose 2$.
A new and simpler proof is given of Salowe's theorem, i.e.,
a sequential algorithm is given that computes the
$k$ closest pairs
in the set $S$ in $O(n \log n + k)$ time, using $O(n+k)$
space. The algorithm fits
in the algebraic decision tree model and is,
therefore, optimal. Salowe's algorithm seems difficult to
parallelize. A parallel version of our
algorithm is given for the CRCW-PRAM model. This version
runs in $O((\log n)^{2} \log\log n )$
expected parallel time and has an $O(n \log n \log\log n +k)$
time-processor product.
