A simple randomized sieve algorithm for the closest-pair problem

Samir Khuller, Yossi Matias

Research output: Contribution to journalArticle

38 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)34-37
Number of pages4
JournalInformation and Computation
Volume118
Issue number1
DOIs
StatePublished - Apr 1995

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'A simple randomized sieve algorithm for the closest-pair problem'. Together they form a unique fingerprint.

  • Cite this