Multirobot Watchman Routes in a Simple Polygon
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908275674447872 |
|---|---|
| author | Mitchell, Joseph S. B. Nguyen, Linh |
| author_facet | Mitchell, Joseph S. B. Nguyen, Linh |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_21034 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Multirobot Watchman Routes in a Simple Polygon Mitchell, Joseph S. B. Nguyen, Linh Computational Geometry 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. |
| title | Multirobot Watchman Routes in a Simple Polygon |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2405.21034 |