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$.
An 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.
