This study explores a variant of the multiple watchmen problem aimed at ensuring that every point within a polygon $P$ is observed from multiple directions. We seek two routes $W_1$ and $W_2$, such that every point $p \text{ in } P$ lies on a segment $\overline{w_1w_2} \text{ in } P$, where $w_1 \text{ in } W_1$ and $w_2 \text{ in } W_2$. We call these routes segment watchman routes.
We demonstrate that finding the optimal routes under the min-max criterion is weakly NP-hard even in simple polygons, while finding optimal routes under the min-sum criterion is NP-hard in polygons with holes.
Moreover, we present sufficient conditions for routes to be segment watchman routes and provide a polynomial-time 2-approximation for both the min-max and min-sum criteria in simple polygons. Finally, we show how to generalize our results for $k$ watchmen.
Blogger's Review: This paper introduces the concept of segment watchman routes, offering fresh insights into the multiple watchmen problem. The proposed approximation algorithms provide feasible solutions to NP-hard challenges, making it a significant contribution with both theoretical and practical implications.