Segment Watchman Routes

Motivated by applications for robust guarding, we consider a variant of the multiple-watchmen problem that ensures that every point within a polygon P is seen from more than one direction: we search for two routes W1, W2, such that every point p ∈ P is contained in a segment w1w2 ⊆ P such that w1 ∈ W1 and w2 ∈ W2. We call such routes segment watchman routes. We show that finding the two routes that are optimal with respect to the min-max criterion is weakly NP-hard even in simple polygons, and that finding the routes that are optimal with respect to 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 under both the min-max criterion and the min-sum criterion, both in simple polygons. Finally, we show how to generalize our results for k watchmen.