Approximating the Smallest $k$-Enclosing Geodesic Disc in a Simple Polygon

Abstract

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(k^{2}n+k^{2}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((n^2/k)\log n\log r+m)$ worst-case time with $O(n+m)$ space. The second algorithm runs in $O(n{\log }^{2}n\log r+m)$ expected time using $O(n+m)$ expected space, independent of $k$. Note that the first algorithm is faster when $k\in \omega (n/\log n)$.

51 pages (27 main content, 4 of references, then appendices), 10 figures (2 of which have 2 subfigures), preliminary version in WADS vol. 14079 of LNCS, pgs. 179 - 192, Springer, 2023