# MPI-I-92-134

## Sequential and parallel algorithms for the k closest pairs problem

### Lenhof, Hans-Peter and Smid, Michiel

#### August 1992, 18 pages.

.

##### Status: available - back from printing

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.

**URL to this document: **https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1992-134

**BibTeX**
`@TECHREPORT{``LenhofSmid92b``,`

` AUTHOR = {Lenhof, Hans-Peter and Smid, Michiel},`

` TITLE = {Sequential and parallel algorithms for the k closest pairs problem},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-92-134},`

` MONTH = {August},`

` YEAR = {1992},`

` ISSN = {0946-011X},`

`}`