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.