Computational aspects of disks enclosing many points

Abstract

Let $S$ be a set of $n$ points in the plane. We present several different algorithms for finding a pair of points in $S$ such that any disk that contains that pair must contain at least $cn$ points of $S$, for some constant $c>0$. The first is a randomized algorithm that finds a pair in $O(n\log n)$ expected time for points in general position, and $c=1/2-\sqrt{(1+2\hat{I}\pm )/12}$, for any $0<\hat{I}\pm <1$. The second algorithm, also for points in general position, takes quadratic time, but the constant $c$ is improved to $1/2-1/\sqrt{12}\approx 1/4.7$. The second algorithm can also be used as a subroutine to find the pair that maximizes the number of points inside any disk that contains the pair, in $O(n^2\log n)$ time. We also consider variants of the problem. When the set $S$ is in convex position, we present an algorithm that finds in linear time a pair of points such that any disk through them contains at least $n/3$ points of $S$. For the variant where we are only interested in finding a pair such that the diametral disk of that pair contains many points, we also have a linear-time algorithm that finds a disk with at least $n/3$ points of $S$. Finally, we present a generalization of the first two algorithms to the case where the set $S$ of points is coloured using two colours. We also consider adapting these algorithms to solve the same problems when $S$ is a set of points inside of a simple polygon $P$, with the notion of a disk replaced by that of a geodesic disk.