# Constant-Time Complete Visibility for Robots with Lights: The Asynchronous Case +
## 4 \(\mathcal{O}(1)\)-Time \(\mathcal{ASYNC}\) Complete Visibility Algorithm
\begin{table}
\begin{tabular}{c l} \hline \hline
**Stages** & **Synchronization Conditions** \\ \hline
0 \& 1.1 & When Stage 0 starts, all robots have color start, and each robot sees, \\  & at most, two other robots collinear with it. \\  & When Stage 1.1 starts, all robots have color start or ready. \\  & Each robot sees at least two other robots not collinear with it. \\ \hline
1.1 \& 1.2 & When Stage 1.2 starts, each interior robot of \(\mathbf{P}^{\prime}\) sees at least one robot with \\  & color corner2, and all corners have color corner, corner2, or corner3. \\ \hline
1.2 \& 1.3 & When Stage 1.3 starts, at least one robot has color corner4, and \\  & all corners have color corner, corner4, or corner5. \\ \hline
1.3 \& 1.4 & When Stage 1.4 starts, there are robots with color internal, \\  & internal\_moving, or corner4, and at least one \\  & robot has color corner5. \\ \hline
1.4 \& 1.5 & When Stage 1.5 starts, the only possible robot colors are corner, side2, \\  & side1, and special. \\ \hline
1.5 \& 2 & When Stage 2 starts, all robots of \(\mathcal{Q}\) are on the corners and sides of \(\mathbf{P}^{\prime\prime}\) \\  & with color corner and side, respectively. \\  & When Stage 2 finishes, all the robots in \(\mathcal{Q}\) are in the corners of \(\mathbf{P}^{\prime\prime\prime}\) \\  & with color corner. \\ \hline \hline \end{tabular}
\end{table} 
Table 3: An illustration of how the colors of robots synchronize execution of the stages. of the framework, if there is no robot currently in transit to the curve. This turned out to be particularly challenging for Stages 1.2 and 1.3, among the other conditions listed in Definition 2. We managed to address this challenge by exploiting the eligible area \(EA(*)\) of the corners of \(\mathbf{P}\). Notice that all the points inside \(EA(c_{i})\) for each corner \(c_{i}\) are visible to all the robots in the interior of \(\mathbf{P}\) (while they are not moving). Therefore, we first develop a technique to compute an eligible line \(EL_{i}\) for each corner \(c_{i}\) of \(\mathbf{P}\) by the interior robots of \(\mathbf{P}\). We then develop a technique to place (at least) four interior robots on an eligible line \(EL_{i}\) (note that \(EL_{i}\) is inside \(EA(c_{i})\)), two as left beacons and two as right beacons (Definition 3). After that, we develop a technique to maintain the property that the interior robots always see \(c_{i}\) (irrespective of the robots on \(EL_{i}\)), and, when there is no transient robot, they see all the robots on \(EL_{i}\). This idea also turned out to satisfy the remaining three conditions (Definition 2) of the Beacon-Directed Curve Positioning framework. Putting these ideas altogether achieves \(\mathcal{O}(1)\) runtime for Stages 1.2 and 1.3. We then extend these techniques in the same spirit to run Stages 1.5 and 2 in \(\mathcal{O}(1)\) time. We provide details of Stages 0-2 separately below and outline the major properties they satisfy. **5. Stage 0-Initialization**  
The goal of this stage is to transform a collinear initial configuration \(\mathbf{C}_{0}\) to a non-collinear \(\mathbf{C}_{0}\). Initially at \(\mathbf{C}_{0}\), all \(N\geq 1\) robots are stationary and have color start. Let \(C\) denote the condition that a robot \(x\) can see only one other robot \(y\) (for \(C\) to be true for \(x\), all robots in \(\mathcal{Q}\) must be collinear with \(x\) a robot at one end of the line). Otherwise, this stage is not needed since all the robots in \(\mathcal{Q}\) are already on the corners, sides, and interior of a hull \(\mathbf{P}\) with (at least) three corners. If \(C\) holds, \(x\) sets its color to start_moving and moves perpendicular to line \(\overline{xy}\) for a small distance \(\delta\). Robot \(x\) then changes its color to ready when it becomes active next time. When at least one robot does this move, the configuration changes to a non-collinear configuration for \(N>3\) (see Figure 8). The cases of \(N\leq 3\) can be treated separately as special cases.