Loading [MathJax]/extensions/tex2jax.js
The Sur­veil­lance Tour prob­lem
Bengt Nils­son
Malmo Uni­ver­sity

The short­est watch­man tour of an en­vi­ron­ment is the short­est closed tour that sees all points of an en­vi­ron­ment. A rea­son­able ex­ten­sion of this con­cept is to re­quire that the tour min­i­mizes the hid­ing time of the points in the en­vi­ron­ment, i.e., the max­i­mum time dur­ing which any points is not seen by the agent fol­low­ing the tour at unit speed. We call such tours {\em sur­veil­lance tours}.

We pro­vide ap­prox­i­ma­tion bounds for some geo­met­ric vari­ants of the sur­veil­lance tour prob­lem, ex­tend the prob­lem, in par­tic­u­lar, to the graph set­ting and re­quest help with prov­ing a non-triv­ial lower bound in this set­ting.