# Constant-Time Complete Visibility for Robots with Lights: The Asynchronous Case +
## 1 Introduction
### Contributions  
The robot model used in this paper is the same one as in [PERSON] et al. [5]; namely, robots are oblivious except for a persistent light that can assume a constant number of colors. The robots considered here are points. If robots have mass and occupy an area (and volume), then the algorithm we present will not work, and a different algorithm needs to be designed that works respecting the mass of the robots. There is a line of work that solves Complete Visibility for the robots with mass; please refer to Reference [10; 11; 12] for some of the most recent works in that line of work. Robots' visibility can be obstructed by other robots in the line of sight, robots are unaware of the number, \(N\), of robots in the swarm, and the robots may be disoriented. Further, we assume that the robot setting is _asynchronous_, i.e., there is no notion of common time and robots perform their Look-Compute-Move cycles at arbitrary time. Robot moves robots are _rigid_, i.e., a robot in motion cannot be stopped (by an adversary) before it reaches its destination point. Our algorithms are collision-free; that is, two robots do not head to the same destination, and their paths of motion do not cross. In Section 3, we develop a framework called Beacon-Directed Curve Positioning that moves a set of robots onto a (\(k\)-point) curve in \(\mathcal{O}(\log k)\) time using three colors in the asynchronous setting, under the condition that \(2k\) robots (called beacons) are already properly laid out on the curve. Furthermore, robots move need to be collision-free, and their paths cannot intersect the curve at more than one point (Definition 2). Using this framework, we prove the following result (comparison is in Table 1), which, to our knowledge, is the first algorithm for Complete Visibility that achieves sub-linear runtime for robots with lights in the asynchronous setting. In fact, this runtime is asymptotically optimal as \(\Omega(1)\) is a trivial lower bound for the problem. Theorem 1: _For any initial configuration of \(N\geq 1\) robots with lights in distinct positions on a real plane, there is an algorithm that solves Complete Visibility in the asynchronous setting in \(\mathcal{O}(1)\) time with \(\mathcal{O}(1)\) colors and without collisions._  
Our algorithm is deterministic and has three stages, Stages 0-2, that execute one after another. Stage 0 is needed only if the initial configuration has robots on a straight line; it breaks this initial linear arrangement and places all robots within or on a convex polygon \(\mathbf{P}\) (convex hull of points) in \(\mathcal{O}(1)\) time. After that, Stage 1 places all robots on the corners and sides of a convex polygon \(\mathbf{P}^{\prime\prime}\). (\(\mathbf{P}\) is first transformed to \(\mathbf{P}^{\prime}\), which is completely contained inside \(\mathbf{P}\), and then \(\mathbf{P}^{\prime}\) is transformed to \(\mathbf{P}^{\prime\prime}\). All this happens during Stage 1, which operates in five sub-stages, Stage 1.1-1.5.) Finally, Stage 2 moves each robot on a side of polygon \(\mathbf{P}^{\prime\prime}\) to a corner of a new convex polygon \(\mathbf{P}^{\prime\prime\prime}\) (the points that are positioned on the corners of \(\mathbf{P}^{\prime\prime}\) do not move at this stage). (The precise definitions of all these convex polygons are given later in Section 2). Keys to Stage 1 are _corner moving_, _internal moving_, and the _beacon-directed curve positioning_ procedures that permit all interior robots of \(\mathbf{P}\) to move to the sides of \(\mathbf{P}^{\prime\prime}\) executing each stage in \(\mathcal{O}(1)\) time, even in the asynchronous setting. An important part of Stage 2 is a _corner insertion_ procedure that moves side robots of \(\mathbf{P}^{\prime\prime}\) to corners of \(\mathbf{P}^{\prime\prime\prime}\) in \(\mathcal{O}(1)\) time while retaining convexity. This paper is a combination of the ideas presented in IPDPS'17 [13] and SSS'17 [14].