$k$-Transmitter Watchman Routes (and Some Guarding Problems)

Christiane Schmidt, Linköping University

Date and time: 2pm (New York time), Tuesday, December 6, 2022

Place: On Zoom (details provided on the seminar mailing list)

We focus on the watchman route problem for a $k$-transmitter watchman: standing at point $p$ in a polygon $P$, the watchman can see $q ∈ P$ if $pq$ intersects $P$’s boundary in at most $k$ connected components—$q$ is $k$-visible to $p$. Travelling along the $k$-transmitter watchman route, either all points in $P$ or a discrete set of points $S ⊂ P$ must be $k$-visible to the watchman. We aim to minimize the length of the $k$-transmitter watchman route. We highlight some special properties of $k$-transmitter watchmen and show that even in simple polygons the $k$-transmitter watchman route problem for $S ⊂ P$ is NP-complete and cannot be approximated to within a logarithmic factor—both if a starting point for the route is given and if no such point exists. Moreover, we present a polylogarithmic approximation for the $k$-transmitter watchman route problem for a given starting point and $S ⊂ P$ with approximation ratio $O(\log^2(|S| · n) \log \log(|S| · n) \log |S|)$ (with $|P| = n$).

Finally, we will consider some related guarding problems.