Shrinking the Jung radius: Maximizing partial coverage of finite point sets

Abstract

Jung's theorem says that planar sets of diameter $1$ can be covered by a closed circular disk of radius $\frac{1}{\sqrt{3}}$. In this paper we consider a fractional Jung-type problem for finite planar point-sets. Let ${\mathcal{P}}_n$ be the family of all finite sets of $n$ points in the plane, of diameter at most $1$. Let the function value $N_n(r)$ ($0<r\le 1$) be the largest integer $k$ so that for every point set $P\in {\mathcal{P}}_n$ there is a closed circular disk of radius $r$ which covers at least $k$ points of $P$. We focus on the radii $r=\frac{1}{2}$ and $r=\frac{1}{4}$ and prove exact maximum values. Concerning the radius $r=\frac{1}{2}$, we prove $N_n(\frac{1}{2})=\lceil \frac{n}{3}\rceil +1$. Concerning the radius $r=\frac{1}{4}$, we prove that $N_n(\frac{1}{4})=\lceil \frac{n}{7}\rceil$ if $n$ is not a multiple of 7, and $N_n(\frac{1}{4})$ is $\frac{n}{7}$ or $\frac{n}{7}+1$ otherwise. We also initiate further study of the function $N_n(r)$ by giving lower and upper bounds for $N_n(r)$ ($0<r<\frac{1}{\sqrt{3}}$).