# \(k\)-Circle Formation and \(k\)-epf by Asynchronous Robots
## 4 Algorithm
### Moveto Destination
We say that there has been significant progress in the time interval \(t\) to \(t^{\prime}\) if \(V_{j}(t^{\prime})<V_{j}(t)\), i.e., one of the following conditions holds:

1. \(n_{k}(t^{\prime})<n_{k}(t)\), or
2. \(n_{k}(t^{\prime})=n_{k}(t)\) and \(N_{j}(t^{\prime})<N_{j}(t)\), or
3. \(n_{k}(t^{\prime})=n_{k}(t)\) and \(N_{j}(t^{\prime})=N_{j}(t)\) and \(d_{j}(t^{\prime})+\delta\leq d_{j}(t)\). Lemma 4: _Let \(t^{\prime}\) be an arbitrary point of time before \(r_{i}\) reaches its destination computed at time \(t\). During an execution of \(AlgorithmOneAxis(C(t))\), execution of \(\mathit{MovetoDestination}(C(t),f_{j},r_{i})\) ensures that \(d_{j}(t^{\prime})+\delta\leq d_{j}(t)\)._

Proof of Lemma 4: Let \(P\) and \(P^{\prime}\) be the selected movement paths for \(r_{i}\) at time \(t\) and \(t^{\prime}\), respectively. We have \(d_{j}(t)=d(r_{i}(t),s(t))\) and \(d_{j}(t^{\prime})=d(r_{i}(t^{\prime}),s(t^{\prime}))\). Note that \(q(t)=s(t)\) implies that the destination point lies on \(C(f_{j},\rho)\). Consider the following cases:

**Case 1. **\(q(t)=s(t)\) and \(p(t)\) does not contain any robot position. This is the case where the robot moves straight towards \(f_{j}\), i.e., \(P=\overline{r_{i}(t)f_{j}}\) and the destination point \(q(t)\) lies on \(C(f_{j},\rho)\) (Step 25 of Algorithm 1). At time \(t^{\prime}\) there would not be any robot on \(q(t)\) and \(r_{i}\) would continue along the same path. Since \(\delta\) is the minimum displacement in a round, \(d_{j}(t^{\prime})+\delta\leq d_{j}(t)\). Recall that \(p(t)\) denotes the intersection point between \(C(f_{j},\rho)\) and \(\overline{r_{i}f_{j}}\). The movements are shown in Figure 9.

**Case 2. **\(q(t)=s(t)\) and \(p(t)\) contains a robot position. There are robot positions on \(C(f_{j},\rho)\), that are not collinear with \(r_{i}\) and \(p(t)\). By step 36 of Algorithm 1 robot \(r_{i}\) computes the movement path \(P\) and destination point \(q(t)\). It starts moving towards \(q(t)\) along \(P\). At time \(t^{\prime}>t\), let \(s(t^{\prime})\) be the intersection point between \(C(f_{j},\rho)\) and \(\overline{r_{i}(t^{\prime})f_{j}}\). Note that, \(p(t^{\prime})\) is not a robot position. Robot \(r_{i}\) selects \(P^{\prime}=\overline{r_{i}(t^{\prime})f_{j}}\) and \(q(t^{\prime})=p(t^{\prime})\). We have \(d(r_{i}(t^{\prime}),q(t))>d(r_{i}(t^{\prime}),q(t^{\prime}))\) and \(d(r_{i}(t),q(t))-d(r_{i}(t^{\prime}),q(t^{\prime}))>d(r_{i}(t),q(t))-d(r_{i}(t^{ \prime}),q(t))\geq\delta\). This implies that \(d_{j}(t^{\prime})+\delta\leq d_{j}(t)\). The movements are shown in Figure 10.

**Case 3. **\(q(t)=s(t)\) and \(p(t)\) contains a robot position. There are no robots on \(C(f_{j},\rho)\), other than being collinear with \(r_{i}\) and \(f_{j}\). By step 30 of Algorithm 1 robot \(r_{i}\) computes the movement path \(P\) and destination point \(q(t)\). This case is similar to case 2. The movements are shown in Figure 11.

**Case 4. **\(q(t)=s(t)\) and \(p(t)\) contains a robot position. There are no robots on \(C(f_{j},\rho)\), other than being collinear with \(r_{i}\) and \(f_{j}\). By step 30 of Algorithm 1 robot \(r_{i}\) computes the movement path \(P\) and destination point \(q(t)\). This case is similar to case 2. The movements are shown in Figure 11.

**Case 4**. : \(q(t)\
eq s(t)\). In this case \(q(t)\) lies on a saturated circle \(C(f_{u},\rho)\) for some \(f_{u}\
eq f_{j}\). Note that, \(C(f_{u},\rho)\) is the first circle, that \(r_{i}\) cuts while moving along \(\overline{r_{i}(t)f_{j}}\). First, consider the case in which \(P=\overline{r_{i}(t)q}\) and \(q(t)=q\) (Step 43 of Algorithm 1), where \(q\) is intersection point between \(\overline{r_{i}(t)f_{j}}\) and \(C(f_{u},\rho)\), which is at closest distance from \(r_{i}\). Since \(\delta\) is the minimum displacement in a round, \(d_{j}(t^{\prime})+\delta\leq d_{j}(t)\). The movements are shown in (Figure 12). Next, consider the case in which \(r_{i}\) computes its movement path \(P\) by step 49 of Algorithm 1. It starts moving towards \(q(t)\) along path \(P\).