# \(k\)-Circle Formation and \(k\)-epf by Asynchronous Robots
## 4 Algorithm
### Moveto Destination
Hence, \(r_{i}\) would not collide with any other candidate robots in the time interval \([t^{\prime},t^{\prime\prime}]\). Theorem 1 characterizes all the configurations and the values of \(k\) for which the \(k\)-circle formation problem is deterministically unsolvable. For some \(k>0\), if the \(k\)-circle formation problem is deterministically solvable for a given \(C(0)\), the robots can identify it in its look phase. The robots must ensure that such configurations would not transform into an configuration that would satisfy the unsolvability criterion (Theorem 1) for any \(t>0\) during an execution of \(AlgorithmOneAxis\). **Lemma 3**. : _Given \(k>0\) and \(C(0)\), if the \(k\)-circle formation problem is deterministically solvable, then at any arbitrary point of time \(t>0\) the configuration would not satisfy the unsolvability criterion (Theorem 1)._

Proof of Lemma 3.: Since the \(k\)-circle formation problem is deterministically solvable for every even value of \(k\), we assume that \(k\) is odd. Note that all the initial configurations, in which \(F\) is asymmetric about the \(y\)-axis or in which \(F_{y}=\emptyset\), would never satisfy the unsolvability criterion stated in Theorem 1. So we only need to consider all the initial configurations in which \(F\) is symmetric about the \(y\)-axis and \(F_{y}\
eq\emptyset\). So, \(C(0)\
otin\mathcal{I}_{1}\cup\mathcal{I}_{4}\). Furthermore, \(C(0)\
otin\mathcal{I}_{5}\) (Otherwise, initially it would have been unsolvable). Therefore, \(C(0)\in\mathcal{I}_{2}\cup\mathcal{I}_{3}\). We have the following cases:

**Case 1. ** The robots make an agreement on the positive direction of \(x\)-axis, which remains invariant for any \(t>0\) (Lemma 1). Since the agreement remains invariant, even if the configuration becomes symmetric about the \(y\)-axis, the configuration will not satisfy the unsolvability criterion stated in Theorem 1 for any \(t>0\). **Case 2. ** The robots decide to transform \(C(0)\) into an unbalanced configuration, in order to make an agreement on the positive direction of \(x\)-axis. This includes the following configurations:

1. \(C(0)\in\mathcal{I}_{3}\). 2. \(C(0)\in\mathcal{I}_{2}\) and it is balanced with at least one unsaturated fixed point in both the half-planes and \(R_{y}(t)\
eq\emptyset\). Let \(t^{\prime}\) be earliest possible point of time at which it becomes unbalanced. In the time interval \(0\) to \(t^{\prime}\), only the topmost robot on the \(y\)-axis would move along the \(y\)-axis. As a result, the configuration would not satisfy the unsolvability criterion (Theorem 1) for any \(t\in[0,t^{\prime})\). At \(t^{\prime}\), the robots make an agreement on the positive direction of \(x\)-axis. Next, the proof follows from case 1. Therefore, \(C(0)\) would not transform into an unsolvable configuration at any arbitrary point of time \(t>0\). Given a configuration \(C(t)\), let \(n_{k}(t)\) denote the number of unsaturated fixed points. The robots may select one or two target fixed points. First, consider the case when the target fixed point is unique. Suppose, \(f_{j}\) is the target fixed point and \(r_{i}\) its candidate robot selected by the robots. Let \(P\) and \(q(t)\) be the movement path and destination point, respectively, computed by \(r_{i}\) at time \(t\), by the execution of \(MovetoDestination(C(t),f_{j},r_{i})\). Consider a straight line along \(P\) towards \(C(f_{j},\rho)\) intersecting the circle \(C(f_{j},\rho)\) first at \(s(t)\) (The line

Figure 8: Robot \(r_{i}\) has moved from \(r_{i}(t_{1})\) to \(r_{i}(t_{2})\). It becomes a candidate robot for \(f_{a}\) at time \(t_{2}\). would always intersect \(C(f_{j},\rho)\)) at time \(t\). Suppose \(d_{j}(t)\) denotes the distance between \(r_{i}(t)\) and \(s(t)\). Let \(N_{i}(t)\) denote the deficit in the number of robots in order to make \(f_{i}\) a saturated fixed point. Let \(V_{j}(t)=(n_{k}(t),N_{j}(t),d_{j}(t))\).