Optimum Guard Covers and $m$-Watchmen Routes for Histograms
Svante Carlsson, Bengt J. Nilsson, Simeon C. Ntafos · 1991
A watchman, in the terminology of art galleries, is a mobile guard. We consider several watchman and guard problems for different classes of polygons. We introduce the notion of vision spans along a path (route) which provide a natural connection between the (stationary) Art Gallery problem, the $m$-watchmen problem and the watchman route problem. We prove that finding the minimum number of vision points (i.e. , static guards) along a shortest watchman route is NP-hard. We provide a linear time algorithm to compute the best set of static guards in a histogram (Manhattan skyline) polygon. The $m$-watchman problem (minimize total length of routes for $m$ watchmen) is NP-hard for simple polygons. We give a $\Theta(n^3+n^2m^3)$-time algorithm to compute the best set of $m$ (moving) watchmen in a histogram.