Shortest Watchman Tours in Simple Polygons under Rotated Monotone Visibility

Abstract

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 $\theta$, while $\theta$ varies in $[0,180^{\circ })$, 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\le r$ is the maximum number of gates of the polygon used at any time in the algorithm.

18 pages, 3 figures, an extended abstract will appear in Proceedings of COCOON 2020 (Lecture Notes in Computer Science)

References in corpus (2)

• Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations
• Capturing points with a rotating polygon (and a 3D extension)