Fixed k-watchman routes under the Min-Max criterion in staircase polygons

In this paper, the problem of multiple watchman routes in staircase polygons is studied. The watchman route problem (WRP) is a variation of the art gallery problem (AGP) in computational geometry, where each point in the given polygon must be visible from at least one point along the route taken by one of the watchmen. A greedy algorithm is presented for the min-max criterion, where we minimize the maximum route length. We assume some starting points of the watchmen may dominate the others. This algorithm finds an optimal solution in O(n² · k² · logn) time, where n represents the number of vertices of the give polygon, and k represents the number of watchmen.