Fast algorithms for computing the smallest k-enclosing circle

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 + δ)r_opt (P, k), where r_opt(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δ³) log ²(1/δ), k)).