A simple randomized sieve algorithm for the closest-pair problem

TitleA simple randomized sieve algorithm for the closest-pair problem
Publication TypeJournal Articles
Year of Publication1995
AuthorsKhuller S, Matias Y
JournalInformation and Computation
Volume118
Issue1
Pagination34 - 37
Date Published1995///
Abstract

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.