2024/02/01 by Prosenjit Bose, Bose, Prosenjit, Anthony D’Angelo +3
Computer Science · Engineering · Social Sciences · #Advanced Numerical Analysis Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Historical Geography and Cartography
paper · pdf · doi:10.48550/arxiv.2402.00336
openalex publication_date 2024/02/01 · openalex created_date 2024/02/03 · openalex updated_date 2026/07/28
We consider the problem of finding a geodesic disc of smallest radius containing at least k points from a set of n points in a simple polygon that has m vertices, r of which are reflex vertices. We refer to such a disc as a SKEG disc. We present an algorithm to compute a SKEG disc using higher-order geodesic Voronoi diagrams with worst-case time O(k2 n + k2 r + min(kr, r(n-k)) + m) ignoring polylogarithmic factors. We then present two 2-approximation algorithms that find a geodesic disc containing at least k points whose radius is at most twice that of a SKEG disc. The first algorithm computes a 2-approximation with high probability in O((n2 / k) log n log r + m) worst-case time with O(n + m) space. The second algorithm runs in O(n log2 n log r + m) expected time using O(n + m) expected space, independent of k. Note that the first algorithm is faster when k ∈ ω(n / log n).