Approximating the Smallest $k$-Enclosing Geodesic Disc in a Simple Polygon
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910313961488384 |
|---|---|
| author | Bose, Prosenjit D'Angelo, Anthony Durocher, Stephane |
| author_facet | Bose, Prosenjit D'Angelo, Anthony Durocher, Stephane |
| contents | 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 ω(n / \log n)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_00336 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximating the Smallest $k$-Enclosing Geodesic Disc in a Simple Polygon Bose, Prosenjit D'Angelo, Anthony Durocher, Stephane Computational Geometry 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 ω(n / \log n)$. |
| title | Approximating the Smallest $k$-Enclosing Geodesic Disc in a Simple Polygon |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2402.00336 |