Computational aspects of disks enclosing many points
arXiv:2601.20036v1 Announce Type: new
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(nlog n)$ expected time for points in general position, and $c = 1/2-sqrt{(1+2alpha)/12}$, for any $0<alpha<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^2log 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.
