TY - JOUR
T1 - A simple randomized sieve algorithm for the closest-pair problem
JF - Information and Computation
Y1 - 1995
A1 - Khuller, Samir
A1 - Matias,Y.
AB - We present a linear time randomized sieve algorithm for the closest-pair problem. Thealgorithm as well as its analysis are simple. The algorithm is extended to obtain a randomized linear time approximation algorithm for the closest bichromatic pair problem.
VL - 118
CP - 1
ER -