Multirobot Watchman Routes in a Simple Polygon

The well-known {Watchman Route} problem seeks a shortest route in a polygonal domain from which every point of the domain can be seen. In this paper, we study the cooperative variant of the problem, namely the {k-Watchmen Routes} problem, in a simple polygon P. We look at both the version in which the k watchmen must collectively see all of P, and the quota version in which they must see a predetermined fraction of P's area. We give an exact pseudopolynomial time algorithm for the {k-Watchmen Routes} problem in a simple orthogonal polygon P with the constraint that watchmen must move on axis-parallel segments, and there is a given common starting point on the boundary. Further, we give a fully polynomial-time approximation scheme and a constant-factor approximation for unconstrained movement. For the quota version, we give a constant-factor approximation in a simple polygon, utilizing the solution to the (single) {Quota Watchman Route} problem.