Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2206.14423 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908836839817216 |
|---|---|
| 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\geq 1$ unit disk robots in the Euclidean plane, we consider the fundamental problem of providing mutual visibility to them: the robots must reposition themselves to reach a configuration where they all see each other. This problem arises under obstructed visibility, where a robot cannot see another robot if there is a third robot on the straight line segment between them. This problem was solved by Sharma et al. [ICDCN, 2018] in the luminous robots model, where each robot is equipped with an externally visible light that can assume colors from a fixed set of colors, using 9 colors and $O(n)$ rounds. In this work, we present an algorithm that requires only 2 colors and $O(n)$ rounds. The number of colors is optimal since at least two colors are required even for point robots [Di Luna et al., Information and Computation, 2017]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2206_14423 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | The Mutual Visibility Problem for Fat Robots with Lights Alsaedi, Rusul J. Gudmundsson, Joachim van Renssen, André Computational Geometry Given a set of $n\geq 1$ unit disk robots in the Euclidean plane, we consider the fundamental problem of providing mutual visibility to them: the robots must reposition themselves to reach a configuration where they all see each other. This problem arises under obstructed visibility, where a robot cannot see another robot if there is a third robot on the straight line segment between them. This problem was solved by Sharma et al. [ICDCN, 2018] in the luminous robots model, where each robot is equipped with an externally visible light that can assume colors from a fixed set of colors, using 9 colors and $O(n)$ rounds. In this work, we present an algorithm that requires only 2 colors and $O(n)$ rounds. The number of colors is optimal since at least two colors are required even for point robots [Di Luna et al., Information and Computation, 2017]. |
| title | The Mutual Visibility Problem for Fat Robots with Lights |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2206.14423 |