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 c n 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 − ( 1 + 2 α ) / 12 , for any 0 < α < 1 . The second algorithm, also for points in general position, takes quadratic time, but the constant c is improved to 1 / 2 − 1 / 12 ≈ 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.

The authors' abstract, as published at the source. Discrete Applied Mathematics, 2026 · DOI ↗