Technical Report No. 45, March 1992 - Abstract

Bengt J. Nilsson, Sven Schuierer:
Shortest m-Watchmen Routes for Histograms: The MinMax Case

In this paper we consider the problem of computing an optimum set of watchmen routes in a histogram. A watchman, in the terminology of art galleries, is a mobile guard and in this version we want to minimize the length of the longest route in the solution. We give an O(n^2*log n) time algorithm to compute the MinMax optimum set of $m$ watchmen in a histogram polygon and we extend the algorithm to solve the Weighted MinMax problem under the same time bound.