We present an O(nrG) time algorithm for computing and maintaining a minimum length shortest watchman tour that sees a simple polygon under monotone visibility in direction θ, while θ varies in [0, 180°), obtaining the directions for the tour to be the shortest one over all tours, where n is the number of vertices, r is the number of reflex vertices, and G ≤ r is the maximum number of gates of the polygon used at any time in the algorithm.
展开▼
