On geodesic disks enclosing many points This is an extended version of a paper appearing in Proceedings of WADS 2025.
Prosenjit Bose, Guillermo Esteban, David Orden, Rodrigo I. Silveira, and Tyler Tuttle · 2025
Read On geodesic disks enclosing many points This is an extended version of a paper appearing in Proceedings of WADS 2025. by Prosenjit Bose, Guillermo Esteban, David Orden, Rodrigo I. Silveira, and Tyler Tuttle (2025) 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-2506-06477.txt.
Introduction
Prosenjit Bose and co-authors bound a covering guarantee for points inside a polygon in a 2025 paper. Distances here are geodesic, meaning paths must stay inside the polygon and bend around its corners. The question: among n scattered points, some pair is so central that any disk through both already captures a guaranteed share of the set.
The guaranteed share lies between about a fifth and a quarter of the points, plus one. For points placed at the corners of a convex-shaped polygon the bound tightens to a third. Two-colored versions, where the pair must differ in color, get their own bounds. The results extend classic ham-sandwich style geometry into walled domains.
Catalog record
| CREATOR | Prosenjit Bose, Guillermo Esteban, David Orden, Rodrigo I. Silveira, and Tyler Tuttle |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 69 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-06477
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On geodesic disks enclosing many points This is an extended version of a paper appearing in Proceedings of WADS 2025. Prosenjit Bose, Guillermo Esteban, David Orden, Rodrigo I. Silveira, and Tyler Tuttle Abstract Let Π ( n ) \Pi(n) be the largest number such that for every set S S of n n points in a polygon P P , there always exist two points x , y ∈ S x,y\in S , where every geodesic disk containing x x and y y contains Π ( n ) \Pi(n) points of S S . We establish upper and lower bounds for Π ( n ) \Pi(n) , and show that ⌈ n 5 ⌉ + 1 ≤ Π ( n ) ≤ ⌈ n 4 ⌉ + 1 \left\lceil\frac{n}{5}\right\rceil+1\leq\Pi(n)\leq\left\lceil\frac{n}{4}\right\rceil+1 . We also show that there always exist two points x , y ∈ S x,y\in S such that every geodesic disk with x x and y y on its boundary contains at least n 3 + 5 ≈ ⌈ n 5.2 ⌉ \frac{n}{3+\sqrt{5}}\approx\left\lceil\frac{n}{5.2}\right\rceil points both inside and outside the disk. For the special case where the points of S S are restricted to be the vertices of a geodesically convex polygon we give a tight bound of ⌈ n 3 ⌉ + 1 \left\lceil\frac{n}{3}\right\rceil+1 . We provide the same tight bound when we only consider geodesic disks having x x and y y as diametral endpoints. We give upper and lower bounds of ⌈ n 5 ⌉ + 1 \left\lceil\frac{n}{5}\right\rceil+1 and n 6 + 26 ≈ ⌈ n 11.1 ⌉ \frac{n}{6+\sqrt{26}}\approx\left\lceil\frac{n}{11.1}\right\rceil , respectively, for the two-colored version of the problem. Finally, for the two-colored variant we show that there always exist two points x , y ∈ S x,y\in S where x x and y y have different colors and every geodesic disk with x x and y y on its boundary contains at least ⌈ n 11.3 ⌉ + 1 \lceil\frac{n}{11.3}\rceil+1 points both inside and outside the disk. 1 Introduction Given a set S of n points in the plane in general position—no three of them are collinear and no four of them are cocircular—there always exist two points u,v\in S such that any disk that contains u and v also contains a constant fraction of S . Neumann-Lara and Urrutia [ 18 ] proved that this constant fraction is at least \left\lceil\frac{n-2}{60}\right\rceil . This bound was improved in a series of papers [ 13 , 14 ] culminating in the best known lower bound of about \frac{n}{4.7} by Edelsbrunner et al. [ 12 ] . Hayward et al. [ 14 ] gave an upper bound by constructing a set of n points such that for every pair of points u,v , there exists a disk with u,v on its boundary containing less than \left\lceil\frac{n}{4}\right\rceil points, thereby showing that \left\lceil\frac{n}{4}\right\rceil+1 is an upper bound for the problem. In addition, they studied the problem for point sets in convex position, giving a tight bound of \left\lceil\frac{n}{3}\right\rceil+1 . Another version of the problem is to consider disks in the plane having the points u and v as diametral endpoints [ 2 ] . In this case, a tight bound of \left\lceil\frac{n}{3}\right\rceil+1 for both the convex and non-convex cases was shown. The best known lower bound of \left(\frac{1}{2}-\frac{1}{\sqrt{12}}\right)n+O(1)\approx\frac{n}{4.7} was obtained in multiple ways, see [ 11 , 12 , 22 ] . Edelsbrunner et al. [ 12 ] were the first to show this using techniques related to the order- k Voronoi diagram. Ramos and Viaña [ 22 ] used known results about j -facets of point sets in \mathbb{R}^{3} . In fact, these results allowed Ramos and Viaña to prove that there is always a pair of points such that any disk through them has at least \frac{n}{4.7} points both inside and outside the disk. Generalizations of the original problem to higher dimensions have been studied by Bárány et al. [ 6 ] who proved that any set S\subset\mathbb{R}^{d} of n points in general position contains a subset A of size m=\left\lfloor\frac{1}{2}(d+3)\right\rfloor such that, any ball with A on its boundary, contains at least \frac{m!(d-m-1)!}{d!}n other points of S . Moreover, Bárány and Larman extended the results in [ 18 ] from Euclidean balls to ellipses in \mathbb{R}^{2} and, more generally, to quadrics in \mathbb{R}^{d} [ 5 ] . In particular, they showed that any set S\subset\mathbb{R}^{d} of n points contains a subset A , of size \left\lfloor\frac{1}{4}d(d+3)\right\rfloor+1 , with the property that any quadric through A , contains at least \frac{n}{s2^{s+1}} points of S , where s=\frac{(d+1)(d+2)}{2} . A colored version of the problem has also been studied in the literature: Given a set S of \frac{n}{2} red and \frac{n}{2} blue points in the plane, there always exists a bichromatic pair of points u,v\in S such that any disk containing u and v contains at least a constant fraction of the n points. Prodromou [ 21 ] proved 1 1 1 Using techniques from Edelsbrunner et al. [ 12 ] , a PhD thesis written in Spanish and not published elsewhere had claimed before a lower bound of \frac{23n}{250}\approx\frac{n}{11} [ 24 ] . that any set S\subset\mathbb{R}^{d} colored with k=\lfloor\frac{d+3}{2}\rfloor colors contains a subset A\subset S of k points, one of each color, such that any ball through all points in A contains at least \frac{|S|}{2k3^{k}} points of S , which gives a fraction \frac{n}{36} for points in the plane. This fraction for the two-dimensional case was later improved in [ 11 ] to \left(\frac{1}{2}-\frac{1}{\sqrt{8}}\right)n-o(n)\approx\frac{n}{6.8} . We note that all the upper bounds in the Euclidean setting translate directly to the geodesic setting by enclosing the constructions in a large enough triangle. Thus, in this paper, we focus mainly on the lower bounds and address all variants of the problem in the case where S is a set of n points inside a simple polygon P . In addition, throughout the paper, we consider that n\geq 21 , so that all our results hold. Variant Euclidean setting Geodesic setting (see Def. 1 ) Lower bound Upper bound Lower bound Upper bound \Pi(n) \lfloor\frac{n}{4.7}\rfloor [ 12 ] \lceil\frac{n}{4}\rceil+1 [ 14 ] \lceil\frac{n}{5}\rceil+1 (Thm. 3 ) \lceil\frac{n}{4}\rceil+1 \overline{\Pi}(n) \lceil\frac{n}{3}\rceil+1 [ 14 ] \lceil\frac{n}{3}\rceil+1 [ 14 ] \lceil\frac{n}{3}\rceil+1 (Thm. 6 ) \lceil\frac{n}{3}\rceil+1 \Pi^{in\mbox{-}out}(n) \lfloor\frac{n}{4.7}\rfloor [ 22 ] \lceil\frac{n}{4}\rceil+1 [ 14 ] \lceil\frac{n}{5.2}\rceil+1 (Thm. 5 ) \lceil\frac{n}{4}\rceil+1 \Pi^{diam}(n) \lceil\frac{n}{3}\rceil+1 [ 2 ] \lceil\frac{n}{3}\rceil+1 [ 2 ] \lceil\frac{n}{3}\rceil+1 (Thm. 7 ) \lceil\frac{n}{3}\rceil+1 \Pi^{bichrom}(n) \lfloor\frac{n}{6.8}\rfloor [ 11 ] \lceil\frac{n}{5}\rceil+1 (Thm. 12 ) \lceil\frac{n}{11.1}\rceil+1 (Thm. 10 ) \lceil\frac{n}{5}\rceil+1 (Thm. 12 ) \overline{\Pi}^{bichrom}(n) \lfloor\frac{n}{6.8}\rfloor [ 11 ] \lceil\frac{n}{4}\rceil+1 [ 11 ] \lceil\frac{n}{11.1}\rceil+1 (Thm. 10 ) \lceil\frac{n}{4}\rceil+1 \Pi^{bichrom-in-out}(n) \lceil\frac{n}{11.3}\rceil+1 (Thm. 11 ) \lceil\frac{n}{4}\rceil+1 \lceil\frac{n}{11.3}\rceil+1 (Thm. 11 ) \lceil\frac{n}{4}\rceil+1 Table 1 : Summary of our results, comparing the Euclidean and geodesic settings. Note that non-integer values in the table are approximations, and refer to the corresponding reference for the exact value. We summarize all our results and compare them with the Euclidean setting in Table 1 . In Section 3 , we present an overview of key properties of shortest paths in P (which we refer to as the geodesic setting ), emphasizing both their similarities to and differences from the Euclidean case. It is these