Shortest Paths of Mutually Visible Robots
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908522968514560 |
|---|---|
| author | Alsaedi, Rusul J. Gudmundsson, Joachim van Renssen, André |
| author_facet | Alsaedi, Rusul J. Gudmundsson, Joachim van Renssen, André |
| contents | Given a set of $n$ point robots inside a simple polygon $P$, the task is to move the robots from their starting positions to their target positions along their shortest paths, while the mutual visibility of these robots is preserved. Previous work only considered two robots. In this paper, we present an $O(mn)$ time algorithm, where $m$ is the complexity of the polygon, when all the starting positions lie on a line segment $S$, all the target positions lie on a line segment $T$, and $S$ and $T$ do not intersect. We also argue that there is no polynomial-time algorithm, whose running time depends only on $n$ and $m$, that uses a single strategy for the case where $S$ and $T$ intersect. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_16901 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Shortest Paths of Mutually Visible Robots Alsaedi, Rusul J. Gudmundsson, Joachim van Renssen, André Computational Geometry Given a set of $n$ point robots inside a simple polygon $P$, the task is to move the robots from their starting positions to their target positions along their shortest paths, while the mutual visibility of these robots is preserved. Previous work only considered two robots. In this paper, we present an $O(mn)$ time algorithm, where $m$ is the complexity of the polygon, when all the starting positions lie on a line segment $S$, all the target positions lie on a line segment $T$, and $S$ and $T$ do not intersect. We also argue that there is no polynomial-time algorithm, whose running time depends only on $n$ and $m$, that uses a single strategy for the case where $S$ and $T$ intersect. |
| title | Shortest Paths of Mutually Visible Robots |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2309.16901 |