Watchman tours for polygons with holes

A 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)per(P) and diam(P)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.