We discuss the paper ``Fast Algorithms for Computing the Smallest k-Enclosing Circle'' by Har-Peled and Mazumdar.

This paper considers the following problem: for a set $P$ of $n$ points in the plane and an integer $k\leq n$, find the smallest circle enclosing at least $k$ points of $P$.

We're going to look at two results from this paper.
(a) Given a set $P$ of $n$ points in the plane, and a parameter $k\leq n$, one can compute, in expected linear time, a radius $r$, such that $r_{opt}(P, k) \leq r\leq 2r_{opt}(P, k)$.

(b) Given a set $P$ of $n$ points in the plane and a parameter $k\leq n$, one can compute, in expected $O(nk)$ time, using $O(n+k^2)$ space, the radius $r_{opt}(P, k)$ and a circle $D_{opt}(P, k)$ that covers $k$ points of $P$.