Watchman tours for polygons with holes

AbstractA watchman tour in a polygonal domain (for short, polygon) is a closed curve in the polygon such that every point in the polygon is visible from at least one point of the tour. We show that the length of a minimum watchman tour in a polygon P with k holes is O(per(P)+k⋅diam(P)), where per(P) and diam(P) denote the perimeter and the diameter of P, respectively. Apart from the multiplicative constant, this bound is tight in the worst case. We then generalize our result to watchman tours in polyhedra with holes in 3-space. We obtain an upper bound of O(per(P)+k⋅per(P)⋅diam(P)+k2/3⋅diam(P)), which is again tight in the worst case. Our methods are constructive and lead to efficient algorithms for computing such tours.We also revisit the NP-hardness proof of the Watchman Tour Problem for polygons with holes