Fast algorithms for computing the smallest k-enclosing circle

Sariel Har-Peled, Soham Mazumdar

Research output: Contribution to journalArticlepeer-review

Abstract

For a set P of n points in the plane and an integer k ≤ n, consider the problem of finding the smallest circle enclosing at least k points of P. We present a randomized algorithm that computes in O(nk) expected time such a circle, improving over previously known algorithms. Further, we present a linear time δ-approximation algorithm that outputs a circle that contains at least k points of P and has radius less than (1 + δ)ropt (P, k), where ropt(P, k) is the radius of the minimum circle containing at least k points of P. The expected running time of this approximation algorithm is O(n + n · min((1/kδ3) log 2(1/δ), k)).

Original languageEnglish (US)
Pages (from-to)147-157
Number of pages11
JournalAlgorithmica (New York)
Volume41
Issue number3
DOIs
StatePublished - Jan 1 2005

Keywords

  • Clustering
  • Outliers
  • Shape fitting

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Fast algorithms for computing the smallest k-enclosing circle'. Together they form a unique fingerprint.

Cite this