The Surveillance Tour problem

Bengt Nilsson

Malmo University

The shortest watchman tour of an environment is the shortest closed tour that sees all points of an environment. A reasonable extension of this concept is to require that the tour minimizes the hiding time of the points in the environment, 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 {\em surveillance tours}.

We provide approximation bounds for some geometric variants of the surveillance tour problem, extend the problem, in particular, to the graph setting and request help with proving a non-trivial lower bound in this setting.