Discrete Surveillance Tours in Polygonal Domains

The watchman route of a polygon is a closed tour that sees all points of the polygon. Computing the shortest such tour is a well-studied problem. Another reasonable optimization criterion is to require that the tour mini- mizes the hiding time of the points in the polygon, i.e., the maximum time during which any points is not seen by the agent following the tour at unit speed. We call such tours surveillance routes. We show a linear time 3/2-approximation algorithm for the optimum surveillance tour problem in rectilin- ear polygons using the L_1 -metric. We also present a polynomial time O(polylog w_max )-approximation algo- rithm for the optimum weighted discrete surveillance route in a simple polygon with weight values in the range [1, w_max]