# Constant-Time Complete Visibility for Robots with Lights: The Asynchronous Case +
## 3 Beacon-Directed Curve Positioning
For \(0\leq i<m\), let \(t_{i}\) denote the time when \(r_{i}\) performs its look operation. Let \(u\) be a transient robot that blocks the view of \(b\) from every waiting robot in the set \(\mathcal{R}\). Then, for any distinct \(0\leq i,j<m\), if \(\operatorname{proj}(b)<\operatorname{proj}(r_{i})<\operatorname{proj}(r_{j})\), then \(t_{i}<t_{j}\)._  
Proof. : Without loss of generality, let the x-axis be a horizontal line and let the projection of \(b\) be to the left of the projections of all elements of \(\mathcal{R}\) (see Figure 5(a)). Since \(u\) blocks \(b\) from all robots of \(\mathcal{R}\), we must have \(\operatorname{proj}(b)<\operatorname{proj}(u)<\operatorname{proj}(r_{i})\), for all \(r_{i}\in\mathcal{R}\) (Lemma 3). Suppose that \(\operatorname{proj}(r_{i})<\operatorname{proj}(r_{j})\) and \(t_{i}>t_{j}\). Then, again, the paths of \(r_{i}\) and \(r_{j}\) will have to cross (see Figure 5(c)), providing the necessary contradiction. Remark 1: _An analogous version of the lemma applies to a right beacon, as well._  
Lemma 5: _Let \(b^{\prime}\) be a right beacon and let \(\mathcal{R}=\{r_{i}\;:\;0\leq i<m\}\) be a set of \(m\) waiting robots. For \(0\leq i<m\), let \(t_{i}\) denote the time when \(r_{i}\) performs its look operation. For any distinct \(0\leq i,j<m\), let \(\operatorname{proj}(r_{i})<\operatorname{proj}(r_{j})\) and let \(t_{i}<t_{j}\). Then, a transient robot \(u\) can block the view of \(b^{\prime}\) from at most one waiting robot from \(\mathcal{R}\)._  
Proof. : Suppose there exist distinct \(i,j\) such that a single transient robot \(u\) blocks right beacon \(b^{\prime}\) from the view of both waiting robots \(r_{i},r_{j}\). Then, \(\operatorname{proj}(u)\) must lie between \(\operatorname{proj}(b^{\prime})\) and \(\operatorname{proj}(\{r_{i},r_{j}\})\). Without loss of generality, let \(\operatorname{proj}(r_{i})<\operatorname{proj}(r_{j})<\operatorname{proj}(u)< \operatorname{proj}(b^{\prime})\); this implies that \(t_{i}<t_{j}\) (from the lemma statement). By a result analogous to that of Lemma 4 applied to a right beacon \(b^{\prime}\), we have \(t_{i}>t_{j}\); this provides the necessary contradiction so that \(u\) cannot block \(b^{\prime}\) from the view of more than one waiting robot. Figure 6: An illustration of the proofs of Lemmas 3 and 4: (**a**) illustrates no path crossing for the robots even when the transient robot \(u\) blocks the beacon \(b\) from \(r_{i}\) and/or \(r_{j}\) when they move, and (**b**,**c**) illustrate a path crossing scenario. Lemma 4 orders the \"look-times\" of waiting robots that are blocked from viewing a left beacon by a single transient robot. Given this order, Lemma 5 shows that each right beacon will have to be blocked by a different transient robot, for the same set of waiting robots. For left and right beacons \(b,b^{\prime}\) and waiting robots \(r_{0},\ldots,r_{m-1}\), in order from left to right, observe that, at the time instant at which \(r_{0}\) looks and transient robot \(u\) blocks \(b\) from \(r_{0}\), some transient \(w\) blocks \(b^{\prime}\) from \(r_{0}\), and \(w\) cannot block the view of \(b^{\prime}\) from \(r_{1},\ldots,r_{m-1}\) when they look. The following result captures this observation. Lemma 6: _Let \(b,b^{\prime}\) be left and right beacons and let \(\mathcal{R}=\{r_{i}\::\:0\leq i<m\}\) be a set of \(m\) waiting robots. Let \(u\) be a transient robot that blocks the view of \(b\) from every waiting robot in \(\mathcal{R}\). Then, at least \(m\) transient robots are needed to block \(b^{\prime}\) from the view of all waiting robots of \(\mathcal{R}\)._  
Proof. : By Lemma 3, \(\mathsf{proj}(b)<\mathsf{proj}(u)<\mathsf{proj}(r_{i})\), for every \(r_{i}\in\mathcal{R}\). Without loss of generality, let \(\mathsf{proj}(r_{i})<\mathsf{proj}(r_{i+1})\), for any \(0\leq i<m-1\). Therefore, by Lemma 4, \(t_{i}<t_{i+1}\); again, \(t_{i}\) is the time when \(r_{i}\) looks. For the right beacon \(b^{\prime}\), we have \(\mathsf{proj}(r_{i})<\mathsf{proj}(r_{i+1})<\mathsf{proj}(b^{\prime})\) with \(t_{i}<t_{i+1}\).