id: 05473983
dt: j
an: 05473983
au: Lenhof, Hans Peter; Smid, Michiel
ti: Sequential and parallel algorithms for the $k$ closet pairs problem.
so: Int. J. Comput. Geom. Appl. 5, No. 3, 273-288 (1995).
py: 1995
pu: World Scientific, Singapore
la: EN
cc: I.3.5 D.1.3 F.2.2 F.1.2
ut: sequential algorithm; salowe’s algorithm; parallel algorithms
ci: 
li: doi:10.1142/S0218195995000167
ab: Summary: 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\atopwithdelims\left(\right)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. Finally, actual running times are given of an
    implementation of our sequential algorithm.
rv: