# MPI-I-92-134

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

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

**MPI-I-92-134**. August** **1992, 18 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

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.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

MPI-I-92-134.pdf | 11734 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://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},`

`}`