Approximating Watchman Routes

Given a connected polygonal domain P, the watchman route problem is to compute a shortest path or tour for a mobile guard (the “watchman”) that is required to see every point of P. While the watchman route problem is polynomially solvable in simple polygons, it is known to be NP-hard in polygons with holes. We present the first polynomial-time approximation algorithm for the watchman route problem in polygonal domains. Our algorithm has an approximation factor O (log 2 n ). Further, we prove that the problem cannot be approximated in polynomial time to within a factor of c log n, for a constant c > 0, assuming that P≠NP.

Authors

• Joseph S. B. Mitchell

Keywords

No keywords are indexed for this paper.