Multirobot Watchman Routes in a Simple Polygon
<|reference_start|>Multirobot Watchman Routes in a Simple Polygon: The well-known \textsc{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 \textsc{$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 \textsc{$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) \textsc{Quota Watchman Route} problem.<|reference_end|>
@article{mitchell2024multirobot,
    title={Multirobot Watchman Routes in a Simple Polygon},
    author={Joseph S. B. Mitchell and Linh Nguyen},
    journal={36th Canadian Conference on Computational Geometry (CCCG 2024)},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.21034},
    primaryClass={cs.CG}
}