Shortest Watchman Tours in Simple Polygons under Rotated Monotone Visibility
| Autor: | Nilsson, Bengt J., Orden, David, Palios, Leonidas, Seara, Carlos, Żyliński, Paweł |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1007/978-3-030-58150-3_25 |
| Popis: | We present an $O(nrG)$ time algorithm for computing and maintaining a minimum length shortest watchman tour that sees a simple polygon under monotone visibility in direction $\theta$, while $\theta$ varies in $[0,180^{\circ})$, obtaining the directions for the tour to be the shortest one over all tours, where $n$ is the number of vertices, $r$ is the number of reflex vertices, and $G\leq r$ is the maximum number of gates of the polygon used at any time in the algorithm. Comment: 18 pages, 3 figures, an extended abstract will appear in Proceedings of COCOON 2020 (Lecture Notes in Computer Science) |
| Databáze: | arXiv |
| Externí odkaz: |
|