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)).
- Shape fitting
ASJC Scopus subject areas
- Computer Science(all)
- Computer Science Applications
- Applied Mathematics