# Constant-Time Complete Visibility for Robots with Lights: The Asynchronous Case +
## 1 Introduction
### Related Work
The idea was to position all the robots on the corners of a convex hull except the faulty robot that may still be in the interior of the hull in the final configuration. [PERSON] and [PERSON] [16] also showed that Complete Visibility can be solved tolerating, at most, 2 faulty robots under certain assumptions on initial configurations. Recently, [PERSON] et al. [17] assumed a weaker one-axis agreement and presented an algorithm for Complete Visibility in the asynchronous setting that can tolerate any number of faulty robots. An interesting property of their algorithm is that it solves Complete Visibility without arranging (non-faulty) robots on the corners of a convex hull. Complete Visibility was also studied in the classical oblivious robots model (no lights) [1]. [PERSON] et al. [15] provided the first algorithm in this model considering the semi-synchronous setting. [PERSON] et al. [12] then provided an algorithm with runtime \(\mathcal{O}(N)\) in this model under the fully synchronous setting. They also showed that the algorithm of [PERSON] et al. [15] has runtime \(\Omega(N^{2})\). [PERSON] et al. [18] solved Complete Visibility under one-axis agreement in the asynchronous setting. Recently, Complete Visibility was also studied in the so-called _fat robots_ model (with or without lights) [19; 10] in which robots are not points, but non-transparent unit discs with mass occupying certain area. In the fat robots with lights model, [PERSON] et al. [11] provided an \(\mathcal{O}(N)\) runtime Complete Visibility algorithm using 9 colors in the fully synchronous setting under rigid (monotonic) movements. In the fat robots (without lights) model, [PERSON] et al. [12] provided an \(\mathcal{O}(N)\) runtime Complete Visibility algorithm in the semi-synchronous setting under rigid movements, with some assumptions on the initial configurations. Additionally, there is a recent interest in solving Complete Visibility in the grid setting, which discretizes the Euclidean real plane. The grid setting is interesting from the aspect of real applications of robots. [PERSON] et al. [20] provided a solution to Complete Visibility using 11 colors in the grid setting and no runtime analysis. We provided an algorithm with a provable runtime bound keeping the number of colors constant [21]. These solutions do not arrange robots on the corners of a convex hull, in contrast to what we do in this paper. Finally, [PERSON] et al. [22] provided matching lower and upper bounds on arranging robots on a convex hull in the grid setting, analogous to what we do in this paper. Beyond Complete Visibility, the computational power of the robots with lights compared to classical oblivious robots was studied in Reference [2], while the robots are working on the Euclidean plane, and in Reference [23], while the robots are working on graphs. The obstructed visibility, in general, was also considered in the different problems in different settings. One problem that considers obstructed visibility is the problem of uniform spreading of robots on a line [24]. The robots considered there are classical robots [1] (without lights). The fat robots model, in which an individual robot is a unit disc (rather than a point), also assumes obstructed visibility [19; 25; 26; 27; 10]. However, this body of work do not analyze runtime. [PERSON] et al. [28] study the problem of collision-free Gathering classical robots to a small area; however, they do not provide a runtime analysis. Similarly, much work on the classical robot model [29; 30; 24; 31] for Gathering does not have runtime analysis, except in a few cases [32; 33; 34; 35; 36]. Furthermore, [PERSON] et al. [37] considered the robot scattering problem (opposite of Gathering) in the semi-synchronous setting and provided a solution with an expected runtime of \(\mathcal{O}(\min\{N,D^{2}+\log N\})\); here, \(D\) is the diameter of the initial configuration.