2025/06/06 by Prosenjit Bose, Guillermo Esteban, Bose, Prosenjit +7
Mathematics · Computer Science · #Geometric and Algebraic Topology #Computational Geometry and Mesh Generation #Advanced Combinatorial Mathematics
paper · pdf · doi:10.48550/arxiv.2506.06477
Let Π(n) be the largest number such that for every set S of n points in a polygon~ P , there always exist two points x, y ∈ S , where every geodesic disk containing x and y contains Π(n) points of~ S . We establish upper and lower bounds for Π(n), and show that \lceil (n)/(5)\rceil+1 ≤ Π(n) ≤ \lceil (n)/(4) \rceil +1 . We also show that there always exist two points x, y∈ S such that every geodesic disk with x and y on its boundary contains at least (n)/(7+√(37)) ≈ \lceil (n)/(13.1) \rceil points both inside and outside the disk. For the special case where the points of S are restricted to be the vertices of a geodesically convex polygon we give a tight bound of \lceil (n)/(3) \rceil + 1. We provide the same tight bound when we only consider geodesic disks having x and y as diametral endpoints. We give upper and lower bounds of \lceil (n)/(5) \rceil + 1 and (n)/(6+√(26)) ≈ \lceil (n)/(11.1) \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 where x and y have different colors and every geodesic disk with x and y on its boundary contains at least \lceil (n)/(27.1)\rceil+1 points both inside and outside the disk.