# Constant-Time Complete Visibility for Robots with Lights: The Asynchronous Case +
## 3 Beacon-Directed Curve Positioning  
The Beacon-Directed Curve Positioning framework uses robots that we call as beacons to define a curve and to guide other robots from their initial positions to final positions on the curve. The beacons start at their final positions on the curve, and all robots are \(\mathcal{ASYNC}\) robots with lights. Section 4 will use the Beacon-Directed Curve Positioning framework as a tool in constructing an \(\mathcal{O}(1)\) time Complete Visibility algorithm. The destination curve is a \"\(k\)-point curve\" (Definition 1) that the positions of the \(k\) points can specify, so the positions of the \(k\) beacons in the framework determine. **Definition 1**. : _Let \(\mathbb{A}\subset\mathbb{R}\) be a finite interval in the real line. Let \(f:\mathbb{A}\longrightarrow\mathbb{R}\) be a (single-valued) function in which its equation \(y=f(x)\) defines a curve on the plane. A \(k\)-point curve is a function \(f\) such that a set of \(k\) points \(\{(x_{i},f(x_{i}))\ :\ 0\leq i<k\}\) suffices to determine the constants in the equation \(y=f(x)\)._  
For example, the curve can be a straight line that function \(y=ax+c\) describes. Two points on this curve (line) enable one to determine constants \(a\) and \(c\) and so the line. As another example, the curve can be a semicircle that equation \((y-a)^{2}+(x-b)^{2}=c^{2}\) describes. Three points on this curve enable one to determine the constants and the curve. As another example, \(c+1\) points can determine a \(c\)th order polynomial. Note that this section uses a global coordinate system to describe the framework, but the framework works with robots that each have only a local coordinate system. In most robot algorithms, the movement of a robot in the move portion of an LCM cycle is along a straight line. The Beacon-Directed Curve Positioning framework assumes monotonic movement but does not require straight-line movement. So, for this section, we define a _path_\(p_{i}\) in an LCM cycle of robot \(r_{i}\) as a finite curve from initial point \((x_{i},y_{i})\) to final point \((x^{\prime}_{i},y^{\prime}_{i})\). Let \(f:\mathbb{A}\longrightarrow\mathbb{R}\) denote a \(k\)-point curve. Let \(\mathcal{R}=\{r_{i}\,:\,0\leq i<m\}\) denote a set of \(m\) robots with lights. The \"curve positioning\" goal of Beacon-Directed Curve Positioning for each \(r_{i}\) at distinct _initial point_\((x_{i},y_{i})\) is to move \(r_{i}\) to distinct _final point_\((x^{\prime}_{i},y^{\prime}_{i})=(x^{\prime}_{i},f(x^{\prime}_{i}))\) on the \(k\)-point curve. We refer to robots in \(\mathcal{R}\) as \"waiting robots\" as they are waiting to move to the curve. The _left beacons_ are robots \(b_{\ell,j}\), for \(0\leq i<k\), are initially on the curve at points with x-coordinates smaller than the x-coordinates of the final positions of all waiting robots. Similarly, _right beacons_ are robots \(b_{r,i}\), for \(0\leq i<k\), are initially on the curve at points with x-coordinates larger than the x-coordinates of the final positions of all waiting robots. Figure 5 depicts these concepts. **Definition 2**. : _Let \(f:\mathbb{A}\longrightarrow\mathbb{R}\) be a \(k\)-point curve, and let \(\mathcal{R}=\{r_{i}\,:\,0\leq i<m\}\) be a set of waiting robots with paths \(p_{i}\) from initial position \((x_{i},y_{i})\) to final position \((x^{\prime}_{i},f(x^{\prime}_{i}))\). Let \(\mathcal{B}_{\ell}=\{b_{\ell,i}\,:\,0\leq i<k\}\), and \(\mathcal{B}_{r}=\{b_{r,i}\,:\,0\leq i<k\}\) be the sets of left and right beacons placed on \(f\) to the left and right of the robot set \(\mathcal{R}\). Then, the triplet \(\langle f,\mathcal{R},\mathcal{B}_{\ell}\cup\mathcal{B}_{r}\rangle\) is admissible iff the following conditions hold. (a) For distinct \(i,j\), paths \(p_{i}\) and \(p_{j}\) do not intersect. (b) For distinct \(i,j\), any line through the initial position of \(r_{i}\) intersects \(p_{j}\) at, at most, one point. (c) For any \(i\), a line through the initial position of \(r_{i}\) intersects curve \(f\) (within its domain \(\mathbb{A}\)) at exactly one point.