2026-07-24T21:21:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19495 2024-03-06T11:04:08Z ddc:004 open_access

𝒪(log{n})-Time Uniform Circle Formation for Asynchronous Opaque Luminous Robots Feletti, Caterina Mereghetti, Carlo Palano, Beatrice Autonomous mobile robots Opaque robots Luminous robots Pattern formation We study the Uniform Circle Formation (UCF) problem for a distributed system of n robots which are required to displace on the vertices of a regular n-gon. We consider a well-studied model of autonomous, anonymous, mobile robots that act on the plane through Look-Compute-Move cycles. Moreover, robots are unaware of the cardinality of the system, they are punctiform, completely disoriented, opaque, and luminous. Collisions among robots are not tolerated. In the literature, the UCF problem has been solved for such a model by a deterministic algorithm in the asynchronous mode, using a constant amount of light colors and 𝒪(n) epochs in the worst case. In this paper, we provide an improved algorithm for solving the UCF problem for asynchronous robots, which uses 𝒪(log n) epochs still maintaining a constant amount of colors. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Caterina Feletti and Carlo Mereghetti and Beatrice Palano 2024 Is Part Of LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2023.5 urn:nbn:de:0030-drops-194956 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.5 eng https://creativecommons.org/licenses/by/4.0/legalcode