# Item

ITEM ACTIONSEXPORT

Released

Report

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

##### Locator

There are no locators available

##### Fulltext (public)

MPI-I-92-134.pdf

(Any fulltext), 12MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Lenhof, H.-P., & Smid, M.(1992). *Sequential and parallel
algorithms for the k closest pairs problem* (MPI-I-92-134). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B708-9

##### 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.