### Technical Report No. 28, April 1991 - Abstract

**Svante Carlsson, Bengt J. Nilsson, Simeon Ntafos:**

*Optimum Guard Covers and m-Watchmen Routes for Histograms*

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^2*m^3)*-time algorithm to compute the best
set of *m* (moving) watchmen in a histogram.

report28.ps.gz