Weighted Discrete Surveillance Tours in Simple Polygons

The watchman route problem is a well investigatedproblem in which a closed tour inside a polygon thatsatisfies visibility constraints is optimized. We ex-plore a new variant in which a tour needs to see a setof locations inside a polygon so that the maximumtime interval in which those locations are not guarded(the delay) is minimized. We call such tours surveil-lance tours. We show that an algorithm that followsthe ideas of the classic watchman problem providesa 2-approximation to our problem. We then investi-gate the case where each location is associated with aweight that represents the importance of not leavingthe location unguarded for long periods. Thus, thetour is required to see locations with larger weightsmore frequently. We show that this variant is NP-hard and present two approximation algorithms