# Constant-Time Complete Visibility for Robots with Lights: The Asynchronous Case +
## 4 \(\mathcal{O}(1)\)-Time \(\mathcal{ASYNC}\) Complete Visibility Algorithm  
Our algorithm consists of three stages, Stages 0-2. In each stage, the robots make progress on converging toward a configuration where all the robots are in a convex hull (see Figure 7). * **Stage 0 (initialization)** handles the case of a collinear initial configuration. The endpoint robots move a small distance perpendicular to the line, which ensures that, in the resulting configuration, not all robots are collinear. Figures 6(a) and 8 depict a worst case scenario, where all robots are initially collinear. In an \(\mathcal{FSYNC}\) setting, this stage runs for one round [9]. In an \(\mathcal{ASYNC}\) setting, we show later that this stage runs in \(\mathcal{O}(1)\) epochs. * **Stage 1 (interior depletion)** moves all interior robots of \(\mathbf{P}\) to the sides of \(\mathbf{P}^{\prime\prime}\) (Figure 6(c)). Stage 1 achieves this in five sub-stages, Stages 1.1-1.5, that work as follows. **Stage 1.1** starts as soon as the robots in \(\mathbf{C}_{0}\) reach a non-collinear configuration (Figure 9a). Stage 1 moves the corner robots of \(\mathbf{P}\) (Figure 9a) to make them corners of \(\mathbf{P}^{\prime}\) (Figure 9b). * **Stage 1.2** first computes the eligible lines for the corners of \(\mathbf{P}^{\prime}\) and then moves (at least) 4 interior robots of \(\mathbf{P}^{\prime}\) (all these robots have color start) to those eligible lines. Figure 9c illustrates this stage. * **Stage 1.3** moves all the remaining interior robots of \(\mathbf{P}^{\prime}\) to the eligible lines of the corners of \(\mathbf{P}^{\prime}\). Figure 9d shows how the robots in the interior of \(\mathbf{P}^{\prime}\) in Figure 9c move to \(EL_{3}\). * **Stage 1.4** moves the robots on the eligible lines to the sides of \(\mathbf{P}^{\prime}\). Figure 9e shows how the robots on the eligible lines in Figure 9d become side robots of \(\mathbf{P}^{\prime}\). * **Stage 1.5** moves the side robots of \(\mathbf{P}\) and \(\mathbf{P}^{\prime}\) to the sides of \(\mathbf{P}^{\prime\prime}\). Figure 9f shows how the side robots of \(\mathbf{P}\) and \(\mathbf{P}^{\prime}\) in Figure 9e become side robots of \(\mathbf{P}^{\prime\prime}\). Stage 1 starts as soon as the robots in \(\mathbf{C}_{0}\) reach to a non-collinear configuration (Figure 7b). In an \(\mathcal{FSYNC}\) setting, this stage runs for four rounds [9]. In an \(\mathcal{ASYNC}\) setting, we show later that each sub-stage runs on \(\mathcal{O}(1)\) epochs and Stage 1 finishes in \(\mathcal{O}(1)\) epochs. * **Stage 2 (edge depletion)** relocates the side robots of \(\mathbf{P}^{\prime\prime}\) (Figure 7d) to the corners of \(\mathbf{P}^{\prime\prime\prime}\). Figure 7e shows the resulting convex hull. In an \(\mathcal{FSYNC}\) setting, this stage runs for four rounds [9]. In an \(\mathcal{ASYNC}\) setting, we show later that this stage runs for \(\mathcal{O}(1)\) epochs. At the initial configuration \(\mathbf{C}_{0}\), all robots in \(\mathcal{Q}\) have color start. Each robot \(r_{i}\) works autonomously having only the information about \(\mathbf{C}(r_{i})\). If \(\mathbf{P}(r_{i})\) is a line segment and \(N>3\), Stage 0 to a non-collinear \(\mathbf{C}_{0}\). Stage 1 proceeds autonomously until all robots are colored either corner or side. This acts as the starting configuration for Stage 2, which proceeds autonomously until all robots have color corner for their lights. The algorithm then terminates. The robots execute the stages sequentially one after another. One could use (only for brevity of this discussion) a different palette of colors for each stage (while keeping the number of colors used a constant). Thus, the algorithm can explicitly synchronize at the end of each stage, and our analysis can consider each stage separately. We will indicate on high level (for brevity) how robots collectively and consistently detect the end of each stage.