# Constant-Time Complete Visibility for Robots with Lights: The Asynchronous Case +
## 2 Model and Preliminaries
Figure 2 shows \(T(c_{i})\), \(TL_{3}\), \(CL_{3}\), \(CP(c_{3})\), and a \(5\)-corner convex polygon \(\mathbf{P}\) with corners \(c_{0}-c_{4}\). Figure 1: A convex polygon \(\mathbf{P}=(c_{0},c_{1},c_{2},c_{3},c_{4})\) with five corner points \(c_{i}\) and nine side points \(s_{j}\). The figure also illustrates the interior and exterior of side \(\overline{c_{0}c_{1}}\). Eligible Area and Eligible Line  
Let \(c_{i}\) be a corner of \(\mathbf{P}\) and let \(a,b\) be the neighbors (sides or corners) of \(c_{i}\) in the perimeter of \(\mathbf{P}\), and let \(u\), \(w\) be the midpoints of \(\overline{c_{i}a}\), \(\overline{c_{i}b}\), respectively. The _eligible area_ for \(c_{i}\), denoted as \(EA(c_{i})\), is a polygonal subregion inside \(\mathbf{P}\) within triangle \(c_{i}uw\), omitting the lines from each robot to \(c_{i}\)[9]. The eligible areas for any two corners of \(\mathbf{P}\) are disjoint. \(EA(c_{i})\) is computed based on \(\mathbf{C}(c_{i})\) and the corresponding polygon \(\mathbf{P}(c_{i})\). Figure 3 depicts eligible area for \(c_{i}\) where the shaded area is \(EA(c_{i})\). To make sure that all the robots in the interior of \(\mathbf{P}\) see \(c_{i}\) when it moves to a point in \(EA(c_{i})\), the points inside the outer boundary of \(EA(c_{i})\) that are part of the lines \(\overline{c_{i}x}\), connecting \(c_{i}\) with all the robots in \(\mathbf{C}(c_{i})\setminus\{a,b,c_{i}\}\) are not considered as the points of \(EA(c_{i})\). When \(c_{i}\) moves to any point inside \(EA(c_{i})\), two prominent properties of the eligible area hold: (i) all the points in the sides and interior of \(\mathbf{P}\) can see \(c_{i}\) (and vice versa), and (ii) \(c_{i}\) remains as a corner of \(\mathbf{P}\). **Lemma 1** (Reference [9]). : _The eligible area \(EA(c_{i})\) for each corner \(c_{i}\) of \(\mathbf{P}\) is bounded by a non-empty convex polygon. Moreover, when \(c_{i}\) moves to a point inside \(EA(c_{i})\), then \(c_{i}\) remains as a corner of \(\mathbf{P}\) and all internal and side robots of \(\mathbf{P}\) are visible to \(c_{i}\) (and vice versa)._  
It is easy to see that edges \(\overline{c_{i}a}\) and \(\overline{c_{i}b}\) are always in the perimeter of the polygonal subregion \(EA(c_{i})\). Let \(x_{i},y_{i}\) be two points in \(\overline{c_{i}a}\) and \(\overline{c_{i}b}\), respectively, that are also in the perimeter of \(EA(c_{i})\). Points \(x_{i},y_{i}\) can be any point in \(\overline{c_{i}a}\) and \(\overline{c_{i}b}\) between \(c_{i}\) and \(e\) and \(c_{i}\) and \(f\), respectively, where \(e,f\) are the neighbor corners of \(c_{i}\) in \(EA(c_{i})\). We say line \(\overline{x_{i}y_{i}}\) is the _eligible line_ for \(c_{i}\) and denote it by \(EL_{i}\) (Figure 3 illustrates these ideas). **Lemma 2**. : _The eligible line \(EL_{i}\) for each corner \(c_{i}\) of \(\mathbf{P}\) contains no point outside of \(EA(c_{i})\), except for the points intersecting lines from internal robots to \(c_{i}\)._  
Figure 3: Eligible area computation; the shaded area depicts \(EA(c_{i})\). Proof. : This lemma is immediate since the eligible area \(EA(c_{i})\) for each corner \(c_{i}\) of \(\mathbf{P}\) is a non-empty convex polygon (Lemma 1); hence, any line connecting any two points on the perimeter of \(\mathbf{P}\) visits only the points that are in the interior of \(EA(c_{i})\), except for intersections with lines from internal robots to \(c_{i}\). Convex Polygons \(\mathbf{P}\), \(\mathbf{P}^{\prime}\), \(\mathbf{P}^{\prime\prime}\), and \(\mathbf{P}^{\prime\prime\prime}\)  
\(\mathbf{P}\) is the convex polygon of the points in \(\mathcal{Q}\). \(\mathbf{P}^{\prime}\) is the convex polygon connecting the corners of \(\mathbf{P}\) after all of them moved to their eligible areas, \(EA(*)\). \(\mathbf{P}^{\prime\prime}\) is the convex polygon with the corners of \(\mathbf{P}^{\prime}\) and the side robots of \(\mathbf{P}\) from those sides with at least two robots.