$k$-Transmitter Watchman Routes
| Autor: | Nilsson, Bengt J., Schmidt, Christiane |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We consider the watchman route problem for a $k$-transmitter watchman: standing at point $p$ in a polygon $P$, the watchman can see $q\in P$ if $\overline{pq}$ intersects $P$'s boundary at most $k$ times -- $q$ is $k$-visible to $p$. Traveling along the $k$-transmitter watchman route, either all points in $P$ or a discrete set of points $S\subset P$ must be $k$-visible to the watchman. We aim for minimizing the length of the $k$-transmitter watchman route. We show that even in simple polygons the shortest $k$-transmitter watchman route problem for a discrete set of points $S\subset P$ is NP-complete and cannot be approximated to within a logarithmic factor (unless P=NP), both with and without a given starting point. Moreover, we present a polylogarithmic approximation for the $k$-transmitter watchman route problem for a given starting point and $S\subset P$ with approximation ratio $O(\log^2(|S|\cdot n) \log\log (|S|\cdot n) \log(|S|+1))$ (with $|P|=n$). Comment: 14 pages, 6 figures; conference proceedings WALCOM 2022: https://link.springer.com/chapter/10.1007/978-3-031-27051-2_18; updated with some notation changes and minor edits |
| Databáze: | arXiv |
| Externí odkaz: |
|