Computational aspects of disks enclosing many points This is an extended version of a paper appearing in Proceedings of LAGOS 2025.
Prosenjit Bose, Guillermo Esteban, and Tyler Tuttle · 2026
Read Computational aspects of disks enclosing many points This is an extended version of a paper appearing in Proceedings of LAGOS 2025. by Prosenjit Bose, Guillermo Esteban, and Tyler Tuttle (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-20036.txt.
Introduction
Prosenjit Bose, Guillermo Esteban, and Tyler Tuttle solve a covering problem about points in the plane. Given a set of points, they seek a pair with a special property. Any disk that contains both points of the pair must also contain a fixed fraction of all the points. Finding such a pair means finding a location where disks are forced to be crowded.
The authors present several algorithms for the task. This paper is an extended version of a conference paper on the problem. Problems of this kind underlie facility location and clustering, where coverage guarantees matter. A forced-crowding pair certifies density without checking every disk. The work is a neat piece of computational geometry with clean guarantees.
Catalog record
| CREATOR | Prosenjit Bose, Guillermo Esteban, and Tyler Tuttle |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-20036
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Computational aspects of disks enclosing many points This is an extended version of a paper appearing in Proceedings of LAGOS 2025. Prosenjit Bose, Guillermo Esteban, and Tyler Tuttle Abstract Let S S be a set of n n points in the plane. We present several different algorithms for finding a pair of points in S S such that any disk that contains that pair must contain at least c n cn points of S S , for some constant c > 0 c>0 . The first is a randomized algorithm that finds a pair in O ( n log n ) O(n\log n) expected time for points in general position, and c = 1 / 2 − ( 1 + 2 α ) / 12 c=1/2-\sqrt{(1+2\alpha)/12} , for any 0 < α < 1 0<\alpha<1 . The second algorithm, also for points in general position, takes quadratic time, but the constant c c is improved to 1 / 2 − 1 / 12 ≈ 1 / 4.7 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 ) O(n^{2}\log n) time. We also consider variants of the problem. When the set S 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 n/3 points of S 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 n/3 points of S S . Finally, we present a generalization of the first two algorithms to the case where the set S S of points is coloured using two colours. We also consider adapting these algorithms to solve the same problems when S S is a set of points inside of a simple polygon P P , with the notion of a disk replaced by that of a geodesic disk. 1 Introduction Let S be a set of n points in the plane. A disk contains or encloses a point p\in S if p is on the boundary or in the interior of the disk. For any two distinct points p,q\in S , we define C_{S}(p,q) to be the smallest integer such that any disk enclosing p and q encloses at least C_{S}(p,q) points of S . Let \Pi(S) be the largest value of C_{S}(p,q) over all pairs \{p,q\} of points in S , and let \Pi(n) be the minimum value of \Pi(S) over all sets S of n points. The problem of finding the exact value of \Pi(n) was introduced in 1988 by Neumann-Lara and Urrutia [ 21 ] . They show that there exists 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>1/60 . Over the next year or so, the constant factor in this result was improved, culminating in a proof by Edelsbrunner et al. [ 13 ] that there exists a pair of points such that any disk containing that pair also contains at least n/4.7 points of S . Recently, Bose et al. studied this problem in the setting of a simple polygon instead of in the plane [ 9 ] . These results all prove the existence of pairs of points, but none of them consider the algorithmic problem of finding such a pair. That is the focus of this paper. Many of the ideas used to prove existence will be useful in providing us with algorithms both in the Euclidean setting and the geodesic setting. 1.1 Previous work The combinatorial problem was introduced by Neumann-Lara and Urrutia [ 21 ] in 1988, who proved that there exists a pair of points p , q in S with the property that any disk that contains p and q contains at least \lceil(n-2)/60\rceil points of S . They also defined \overline{\Pi}(n) to be the minimum value of \Pi(S) over all sets S of n points in convex position , showing that \overline{\Pi}(n)\geq\lceil(n-2)/4\rceil . Subsequently, Bárány et al. [ 6 ] improved the lower bound to \Pi(n)\geq n/30 . Simultaneously, the problem was considered by Hayward et al. [ 16 ] , who proved that \lfloor n/27\rfloor+2\leq\Pi(n)\leq\lceil n/4\rceil+1 , and \overline{\Pi}(n)=\lceil n/3\rceil+1 . The lower bound for point sets in non-convex position was later improved by Hayward [ 17 ] to \Pi(n)\geq\lceil 5(n-2)/84\rceil . Finally, Edelsbrunner et al. [ 13 ] proved that \Pi(n)\geq\frac{n-3}{2}-\sqrt{\frac{(n-2)^{2}-1}{12}}=\bigg(\frac{1}{2}-\frac{1}{\sqrt{12}}\bigg)n+O(1)\approx\frac{n}{4.7}, which stands as the best lower bound on \Pi(n) . An alternate proof of the same bound was given by Ramos and Viaña [ 25 ] , who showed the stronger result that there always exist two points p and q with the property that any disk which has p and q on its boundary contains at least n/4.7 points, and there are at least n/4.7 points outside of the disk. Another proof of this fact was given by Claverol et al. [ 11 ] using higher-order Voronoi diagrams. Variations of the problem have been studied over the years. Akiyama et al. [ 3 ] proved that there exist two points p and q such that the disk with segment pq as a diameter encloses at least n/3 points. Bárány et al. [ 6 ] considered the problem in \mathbb{R}^{d} . Specifically, they showed that given a set S of n points in \mathbb{R}^{d} , there exists a subset T of S of size \lfloor(d+3)/2\rfloor such that any d-dimensional ball that contains T contains at least cn points of S , for some constant c>0 . Bárány and Larman generalized this further from balls to quadric surfaces [ 7 ] . In addition, a bichromatic version of the problem has been studied in [ 11 , 24 , 26 ] , where the goal is to find a bichromatic pair of points such that any disk that contains the pair must contain many points. The author of [ 24 ] also generalizes this coloured version of the problem to higher dimensions. Many of these variations were generalized from the plane to sets of points contained in a simple polygon by Bose et al. [ 9 ] . They show that given a set S of n points in a simple polygon P , there exist two points of S such that any geodesic disk that contains those two points on its boundary contains at least n/5 points of S . For point sets in geodesically convex position, they prove that there exists a pair such that any geodesic disk containing the pair contains at least n/3 points, matching the bound of the Euclidean setting. They also consider the diametral and bichromatic versions of the problem, as well as the version for points both inside and outside the disk. 1.2 Our results In this paper, we present different algorithms which, given a