Shortest m-watchmen routes for histograms: the minmax case
Bengt J. Nilsson, Sven Schuierer · 2003
The authors 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 one wants to minimize the length of the longest route in the solution. The authors give an O(n/sup 2/ log n) time algorithm to compute the MinMax optimum set of m watchmen in a histogram polygon.>