Fast Algorithms for Computing the Smallest
k-Enclosing Disc

Sariel Har-Peled and Soham Mazumdar

We consider the problem of finding, for a given n point set
P in the plane and an integer k <= n, the smallest
circle enclosing at least k points of P. We present a
randomized algorithm that computes in O(n k) expected time
such a circle, improving over all previously known algorithms.

Since this problem is believed to require Omega(n k) time, we
present a linear time µ-approximation algorithm that
outputs a circle that contains at least k points of P,
and of radius less than (1+ µ)ropt(P,k), where
ropt(P,k) is the radius of the minimal disk 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)).