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.
ASJC Scopus subject areas
- Theoretical Computer Science
- Information Systems
- Computer Science Applications
- Computational Theory and Mathematics