# \(k\)-Circle Formation and \(k\)-epf by Asynchronous Robots
## 4 Algorithm
### Moveto Destination
Notice that if \(f_{j}\) lies on the \(y\)-axis and the configuration is symmetric, there would be two such candidate robots. In that case, we assume that both of them reached \(C(f_{j},\rho)\) at time \(t\). Otherwise, the configuration \(C(t)\) cannot possibly satisfy Property 1. Suppose \(r_{i}\) became a candidate robot at some time \(t_{1}<t\) by the execution of \(CandidateRSelection\). Note that in the time interval \([t_{1},t)\), the distance of \(r_{i}\) from \(f_{j}\) was greater than \(\rho\). Otherwise, the choice of \(t\) is wrong. If there were two candidate robots for \(f_{j}\), then this is true for both the candidate robots. Furthermore, at time \(t_{1}\) there were no robot position (say \(r_{a}\)) such that \(d(f_{j},r_{a}(t))<\rho\). Otherwise, \(r_{a}\) would have been selected as a candidate robot. Notice that the candidate robot(s) was the only robot which was moving towards \(C(f_{j},\rho)\). Therefore, all the robots on \(C(f_{j},\rho)\) are static at \(t\). Next, consider a fixed point \(f_{l}\in F\) such that \(f_{l}\) has higher configuration rank than \(f_{j}\). All the robots within \(\rho\) distance from \(f_{l}\) must lie on \(C(f_{l},\rho)\). This is because, during an execution of \(CandidateRSelection\) for a fixed point, a robot within \(\rho\) distance from that fixed point is given higher preference than any robot at greater than \(\rho\) distance from that fixed point. Since \(C(f_{l},\rho)\) is not oversaturated, all the robots are static at time \(t\). Next, consider a fixed point \(f_{b}\in F\) such that \(f_{b}\) has lower configuration rank than \(f_{j}\). By the choice of \(f_{j}\) and \(r_{i}\), none of the robots within \(\rho\) distance from \(f_{b}\) were selected as a candidate robot. Therefore, all the robots within \(\rho\) distance from \(f_{b}\) are static at time \(t\). Hence, if the configuration \(C(t)\) satisfies Property 1, then none of the robots have any inherent motion in \(C(t)\). Theorem 4: _If the initial configuration \(C(0)\in\{\mathcal{I}_{1}\cup\mathcal{I}_{2}\cup\mathcal{I}_{3}\cup\mathcal{I}_ {4}\cup\mathcal{I}_{5}\}\) and \(C(0)\) does not satisfy the unsolvability criterion stated in Theorem 4, then the robots would eventually solve the \(k\)-epf problem under one axis agreement, by the execution of algorithm \(Algokepf\)._

Proof of Theorem 4.: First, consider the case when the configuration does not satisfy Property 1. The robots would start executing \(AlgorithmOneAxis\). From Theorem 4, it follows that the configuration would eventually satisfy Property 1. Next, consider the case when the configuration satisfies Property 1. From Lemma 10, it follows that all the robots would be static in such a configuration. The robots would start executing \(\mathcal{A}\). During an execution of \(\mathcal{A}\), each robot moves in a straight line by at least \(\delta\) distance, towards the fixed point from which it is at the closest distance. Since \(\rho\) is finite and there are finitely many robots, eventually each of the fixed points will contain exactly \(k\) robots. Hence, the robots would eventually solve the \(k\)-epf problem by the execution of algorithm \(Algokepf\). The above theorem provides an evidence that a deterministic distributed algorithm to solve the \(k\)-circle formation problem can be modified to solve the \(k\)-epf problem and proves Theorem 3. Notice that during an execution of algorithm \(Algokepf\), the robots are only allowed to create a multiplicity on the fixed points. Therefore, the existence of a deterministic distributed algorithm which solves the \(k\)-epf problem, without allowing a robot multiplicity point outside the fixed points, is guaranteed by Theorem 3. ## 7 Conclusions

This paper studies the \(k\)-circle formation problem by asynchronous, autonomous, anonymous and oblivious robots in the Euclidean plane. The problem is investigated in a setting where the robots have an agreement on the direction and orientation of the \(y\)-axis. The following three main results have been proved:

1.