# \(k\)-Circle Formation and \(k\)-epf by Asynchronous Robots
## 4 Algorithm
### Moveto Destination
\(d(r_{i}(t),f_{j})>\rho\) and \(\overline{r_{i}(t)f_{j}}\) does not cut any saturated circle. If \(p(t)\) is not a robot position, then \(r_{i}\) selects \(q(t)=p(t)\) and \(P=\overline{r_{i}(t)p(t)}\) (Figure 3a). Next, consider the case when \(p(t)\) is a robot position and there are no other robot positions on \(C(f_{j},\rho)\) other than those collinear with \(r_{i}\) and \(f_{j}\). In this case, \(r_{i}\) selects one of the tangent lines to \(C(f_{j},\rho)\) from its position (say \(t^{a}\)) as its movement path. Let \(t^{a}\) intersect \(C(f_{j},\rho)\) at \(q\). In this case \(q\) cannot be a robot position. Since \(r_{i}\) is a candidate robot, the line segement \(\overline{r_{i}(t)q}\) cannot possibly contain any robot positions other than \(r_{i}(t)\). It selects \(P=t^{a}\) and \(q(t)=q\) (Figure 3b). Otherwise, among the robot positions on \(C(f_{j},\rho)\) which are not collinear with \(r_{i}\) and \(f_{j}\), let \(r_{k}\) be the robot such that the angle \(\measuredangle\overline{r_{i}(t)f_{j}}r_{i}(t)\overline{r_{i}(t)r_{k}(t)}\) is smallest. Let \(B_{1}\) be the angle bisector such that \(\measuredangle\overline{r_{i}(t)f_{j}}r_{i}(t)B_{1}=\frac{1}{2}\measuredangle \overline{r_{i}(t)f_{j}}r_{i}(t)\overline{r_{i}(t)r_{k}(t)}\). Note that \(B_{1}\) intersects \(C(f_{j},\rho)\) at exactly two points. Between these two points, let \(q_{1}\) be the closest point from \(r_{i}\). By the choice of \(r_{k}\), \(q_{1}\) cannot be a robot position. Furthermore, since \(r_{i}\) is a candidate robot, the line segment \(\overline{r_{i}(t)q_{1}}\) cannot possibly contain any robot positions other than \(r_{i}(t)\). It selects \(q(t)=q_{1}\) and \(P=\overline{r_{i}(t)q_{1}}\) (Figure 4). 2. \(d(r_{i}(t),f_{j})>\rho\) and \(\overline{r_{i}(t)f_{j}}\) cuts some saturated circle. Let \(C(f_{u},\rho)\) be the first saturated circle, which \(r_{i}\) cuts while moving along \(\overline{r_{i}(t)f_{j}}\). Notice that \(\overline{r_{i}f_{j}}\) would intersect \(C(f_{u},\rho)\) at two points. Consider \(q\) to be the intersection point between \(C(f_{u},\rho)\) and \(\overline{r_{i}(t)f_{j}}\), which is at the closest distance from \(r_{i}\). Since \(r_{i}\) is a candidate robot, the line segment \(\overline{r_{i}(t)q}\) (excluding point \(q\)) cannot possibly contain any robot positions other than \(r_{i}(t)\). However, since \(q\) is a point on \(C(f_{u},\rho)\), it may be a robot position. If \(q\) is not a robot position, then \(r_{i}\) selects \(q(t)=q\) and \(P=\overline{r_{i}(t)q}\) (Figure 5). Otherwise, let \(r_{k}\) (not collinear with \(r_{i}\) and \(f_{j}\)) be the robot on \(C(f_{u},\rho)\) such that angle between \(\overline{r_{i}(t)f_{j}}\) and \(\overline{r_{i}(t)r_{k}(t)}\) is the smallest. Since \(C(f_{u},\rho)\) is saturated, such a robot position always exists on it. Let \(B_{1}\) be the angle bisector, such that \(\measuredangle\overline{r_{i}(t)f_{j}}r_{i}(t)B_{1}=\frac{1}{2}min(\measuredangle \overline{r_{i}(t)f_{j}}r_{i}(t)\overline{r_{i}(t)}\overline{r_{i}(t)r_{k}(t)})\). Note that \(B_{1}\) intersects \(C(f_{u},\rho)\) at exactly two points. Between these two points, let \(q_{1}\) be the closest point from \(r_{i}\). By the choice of \(r_{k}\), \(q_{1}\) cannot be a robot position. Furthermore, since \(r_{i}\) is a candidate robot \(\overline{r_{i}(t)q_{1}}\) cannot possibly contain any robot positions other than \(r_{i}(t)\). Robot \(r_{i}\) selects \(P=\overline{r_{i}(t)q_{1}}\) and \(q(t)=q_{1}\) (Figure 6). Note that the choice of \(B_{1}\) ensures that \(r_{i}\) always moves towards \(C(f_{j},\rho)\). 3. \(d(r_{i}(t),f_{j})<\rho\). Let \(l_{ji}(t)\) be the line segment from \(f_{j}\) to \(C(f_{j},\rho)\), passing through \(r_{i}\). Let \(q\) be the intersection point between \(l_{ji}(t)\) and \(C(f_{j},\rho)\). Since \(r_{i}\) is a candidate robot, the line segment \(\overline{r_{i}(t)q}\) (excluding point \(q\)) cannot possibly contain any robot positions other than \(r_{i}(t)\). However, since \(q\) is a point on \(C(f_{j},\rho)\), it may be a robot position.