# Constant-Time Complete Visibility for Robots with Lights: The Asynchronous Case +
## 3 Beacon-Directed Curve Positioning
(d) With all robots in \(\mathcal{R}\) at their initial positions, all \(2k\) beacons in \(\mathcal{B}_{\ell}\cup\mathcal{B}_{r}\) are visible to each \(r_{i}\in\mathcal{R}\)._  
**Definition 3**. : _The Beacon-Directed Curve Positioning Problem is defined as follows: Let \(f:\mathbb{A}\longrightarrow\mathbb{R}\) be a \(k\)-point curve, let \(\mathcal{R}=\{r_{i}\,:\,0\leq i<m\}\), and let \(\mathcal{B}\) be a set of \(k\) left and \(k\) right beacons on \(f\) such that \(\langle f,\mathcal{R},\mathcal{B}\rangle\) is admissible. Let the initial color of each robot \(r_{i}\in\mathcal{R}\) be_ wait_, and let the beacons in \(\mathcal{B}\) be colored_ beacon_. The objective is to move each robot \(r_{i}\in\mathcal{R}\) to its final position on \(f\) and then change its color to_ beacon_._  
The three condition-action pairs below present robot actions to solve the Beacon-Directed Curve Positioning Problem. **Condition 1:** Robot \(r\) has color wait, and it can see at least \(k\) robots with color beacon. **Action 1:** Robot \(r\) changes its color to not-waiting, determines the equation for the \(k\)-point curve, \(f\), and moves monotonically on its path \(p\) to position itself on curve \(f\). **Condition 2:** Robot \(r\) has color not-waiting. **Action 2:** Robot \(r\) changes its color to beacon. **Condition 3:** Robot \(r\) has color beacon, and it cannot see any robot colored wait. **Action 3:** Terminate. Call as a _transient robot_ any robot that is in motion along its path (between its initial and final positions); clearly, a transient robot was a waiting robot at the start of its cycle and is on its way to becoming a beacon at the end of its next cycle. Observe that, if a waiting robot cannot see some beacon, then there must be a transient robot that blocks its view. We now establish conditions on the number of transient robots and the look times of waiting robots required to block the view of beacons from the waiting robots (Lemmas 3-6). Figure 5: An illustration of Beacon-Directed Curve Positioning (BDCP). Red (resp., white) circles denote the initial (resp., final) positions of \(n=4\) robots. Blue circles denote the beacons. Then, we will lower bound the increase in the number of beacons from one epoch to the next (Lemma 7) toward establishing an \(\mathcal{O}(\log k)\) epoch run time for the Beacon-Directed Curve Positioning algorithm. In the remainder of this section, we will implicitly assume in all lemmas that admissibility is satisfied; we also consider any robot with color beacon or not-waiting as a beacon. Recall that all robot movements are monotonic. For any robot \(r_{i}\), define the _projection_ of \(r_{i}\) on a \(k\)-point curve \(f:\mathbb{A}\longrightarrow\mathbb{R}\) (denoted by \(\operatorname{proj}(r_{i})\)) as the x-coordinate, \(x_{i}^{\prime}\), of the final position of \(r_{i}\). For a beacon \(b\), its projection on \(f\) is \(\operatorname{proj}(b)\), the x-coordinate of its position. When applied to a set \(\mathcal{S}\) of robots, \(\operatorname{proj}(\mathcal{S})\) refers to the smallest interval within \(\mathbb{A}\) in which the projections of all elements of \(\mathcal{S}\) lie. Lemma 3: _For left \((\)resp., right\()\) beacon \(b\) and waiting robot \(r_{i}\), if a transient robot \(u\) blocks \(b\) from \(r_{i}\), then \(\operatorname{proj}(b)<\operatorname{proj}(u)<\operatorname{proj}(r_{i})\)\((\)resp., \(\operatorname{proj}(r_{i})<\operatorname{proj}(u)<\operatorname{proj}(b))\)._  
Proof. : Recall that admissibility requires that paths not cross. Suppose \(b\) is a left beacon, then \(\operatorname{proj}(b)<\operatorname{proj}(r_{i})\). If \(\operatorname{proj}(u)>\operatorname{proj}(r_{i})\), then the paths of \(u\) and \(r_{i}\) must cross (see Figure 5(b)), providing the necessary contradiction. The proof for a right beacon is analogous. Lemma 4: _Let \(\mathcal{R}=\{r_{i}\;:\;0\leq i<m\}\) be a set of \(m\) waiting robots and let \(b\) be a left beacon with \(\operatorname{proj}(b)\
ot\in\operatorname{proj}(\mathcal{R})\).