A Simple Randomized Sieve Algorithm for the Closest-Pair Problem

We present a linear time randomized sieve algorithm for the closest-pair problem. The algorithm and its analysis are simple. The algorithm is extended to obtain a randomized linear time approximation algorithm for the closest bichromatic pair problem.

Authors

• S. Khuller
• Y. Matias

Keywords

No keywords are indexed for this paper.