# Constant-Time Complete Visibility for Robots with Lights: The Asynchronous Case +
## 1 Introduction
### Related Work  
The problem of Complete Visibility has been getting much attention recently, after it was proposed for the very first time by [PERSON] et al. [5] in 2014. They proposed the problem on a 2-dimesional real plane and we also consider the problem on the real plane. The most closely related works on a plane are listed in Table 1. [PERSON] et al. [5] designed the first algorithm for robots with lights to solve Complete Visibility. Their algorithm uses 6 colors in the semi-synchronous setting and 10 colors in the asynchronous setting. Their algorithm arranged robots on corners of a convex polygon, which naturally solves this problem. Although other ways exist to solve Complete Visibility without forming a convex hull, such a convex hull solution provides additional advantages [10; 15] in solving some other problems. One example is our recent work on pattern formation [4], where we use the convex hull based Complete Visibility result of this paper in the first step of the four-step algorithm for pattern formation in the asynchronous setting presented in that paper. In this paper, we, too, form a convex hull as a solution to Complete Visibility. [PERSON] et al. [5] established the correctness of their algorithm, including a proof of (finite-time) termination; however, the work does not include a runtime analysis. Subsequent work [6; 7] reduced the number of colors used for the algorithm. The minimum number of colors is 2, and [PERSON] et al. provided 2-color algorithm for the semi-synchronous and asynchronous settings of monotonic robot movements (defined later) and 3-color algorithm in the asynchronous setting with non-monotonic robot movements. Therefore, with respect to optimizing the number of colors, there is not much work left except designing a 2-color algorithm for the asynchronous setting of non-monotonic robot movements. Therefore, the recent focus is mostly on runtime [8; 9], keeping the number of colors constant, i.e., \(\mathcal{O}(1)\). Runtime is a critical factor when robots have to arrange themselves in a target configuration, frequently while working in real-time after being deployed in their work environments. In this direction, [PERSON] et al. [8] designed the first algorithm with \(\mathcal{O}(\log N)\) runtime, and with the use of \(\mathcal{O}(1)\) colors in the fully synchronous setting. [PERSON] et al. [9] improved on this result with \(\mathcal{O}(1)\) runtime using \(\mathcal{O}(1)\) colors in the semi-synchronous setting. Whether this \(\mathcal{O}(1)\) runtime, \(\mathcal{O}(1)\) colors result extends to the asynchronous setting, is an important open question left from these existing works, which we address in this paper by designing such an algorithm that works in \(\mathcal{O}(1)\) time using \(\mathcal{O}(1)\) colors. Of the three models typically considered, fully synchronous, semi-synchronous, and asynchronous, the asynchronous setting is the weakest, and full synchronous is the strongest; asynchronous algorithms present significant challenges in their design and analysis. Therefore, our work considers the problem in the most difficult setting, and, since the algorithm we present works in this most difficult setting, it subsumes all the existing works designed for the relatively simpler fully synchronous and semi-synchronous settings. It is interesting to consider whether Complete Visibility can be solved when robots may experience faults. [PERSON] et al. [6] observed that their Complete Visibility algorithm for non-faulty robots can solve Complete Visibility tolerating a faulty robot if the faulty robot is in the perimeter of the convex hull formed by the initial configuration of the robots. [PERSON] and [PERSON] [16] provided an algorithm that tolerates one faulty robot (irrespective of whether the faulty robot is in the interior or not) when robots have both-axis agreement in the semi-synchronous setting under rigid movements.