2026-10-10T20:33:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24241 2025-11-12T12:39:19Z ddc:004 open_access

On Geodesic Disks Enclosing Many Points Bose, Prosenjit Esteban, Guillermo Orden, David Silveira, Rodrigo I. Tuttle, Tyler Enclosing disks Geodesic disks Bichromatic 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 ⌈n/5⌉ +1 ≤ Π(n) ≤ ⌈n/4⌉ +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 16/665(n-2) ≈ ⌈(n-2)/41.6⌉ 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 ⌈n/3⌉ + 1. We provide the same tight bound when we only consider geodesic disks having x and y as diametral endpoints. Finally, we give a lower bound of ⌈(n-2)/36⌉+2 for the two-colored version of the problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Prosenjit Bose and Guillermo Esteban and David Orden and Rodrigo I. Silveira and Tyler Tuttle 2025 Is Part Of LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WADS.2025.10 urn:nbn:de:0030-drops-242414 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.10 eng https://creativecommons.org/licenses/by/4.0/legalcode