We dis­cuss the paper ``Fast Al­go­rithms for Com­put­ing the Small­est k-En­clos­ing Cir­cle'' by Har-Peled and Mazum­dar.

This paper con­sid­ers the fol­low­ing prob­lem: for a set $P$ of $n$ points in the plane and an in­te­ger $k\leq n$, find the small­est cir­cle en­clos­ing at least $k$ points of $P$.

We're going to look at two re­sults from this paper.
(a) Given a set $P$ of $n$ points in the plane, and a pa­ra­me­ter $k\leq n$, one can com­pute, in ex­pected lin­ear time, a ra­dius $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 pa­ra­me­ter $k\leq n$, one can com­pute, in ex­pected $O(nk)$ time, using $O(n+k^2)$ space, the ra­dius $r_{opt}(P, k)$ and a cir­cle $D_{opt}(P, k)$ that cov­ers $k$ points of $P$.