# \(k\)-Circle Formation and \(k\)-epf by Asynchronous Robots
## 4 Algorithm
### Moveto Destination
Let \(f_{j}\) be the target fixed point. Robot \(r_{k}\) executes \(CandidateRSelection(C(t),f_{j})\). Let \(r_{i}\) be the candidate robot. Note that there may be two candidate robots for \(f_{j}\). In that case, suppose \(r_{i}\) is the candidate robot, that lies in the same half-plane containing \(r_{k}\). If \(r_{k}=r_{i}\), then it executes \(MovetoDestination(C(t),f_{j},r_{i})\). 2. There exists an unsaturated fixed point in \(F\setminus F_{y}\). Note that such unsaturated fixed points are present in both the half-planes. Otherwise the robots would have an agreement on the positive direction of the \(x\)-axis. Robot \(r_{k}\) executes \(TargetFPSelection(C(t))\). In this case there are two target fixed points, one from each of the half-planes. Let \(f_{j}\) and \(f_{u}\) be the two target fixed points. Without loss of generality, assume that \(r_{k}\) and \(f_{j}\) lie in the same half-plane. Next, \(r_{k}\) executes \(CandidateRSelection(C(t),f_{j})\). Let \(r_{i}\) be the candidate robot selected for \(f_{j}\). If \(r_{k}=r_{i}\), then it executes sub-procedure \(MovetoDestination(C(t),f_{j},r_{i})\). ## 5 Correctness

Lemma 1: _Given a configuration \(C(t)\) for some \(t\geq 0\), if the robots agree upon the positive direction of the \(x\)-axis, by the execution of \(AgreementOneAxis(C(t))\), then the agreement remains invariant at any arbitrary point of time \(t^{\prime}>t\)._

Proof of Lemma 1.: Let the robots agree upon the positive direction of the \(x\)-axis, by the execution of \(AgreementOneAxis(C(t))\). Consider the following cases:

**Case 1. **: \(C(t)\in\mathcal{I}_{1}\), i.e., \(F\) is asymmetric about the \(y\)-axis. Since this agreement is w.r.t. the fixed points, it remains invariant for any \(t^{\prime}>t\). **Case 2. **: \(C(t)\in\mathcal{I}_{2}\) and \(C(t)\) is unbalanced. In this case, the agreement on the direction of the positive \(x\)-axis is based upon robot positions. If the robots move across the \(y\)-axis from the negative side to the positive side, then the agreement does not change as the positive side of the \(y\)-axis would still contain the maximum number of robots. During an execution of \(TargetFPSelection(C(t))\), the unsaturated fixed points with a higher configuration rank are given preference over the unsaturated fixed points with a lower configuration rank. As a result, the robots move across the \(y\)-axis from the positive side to the negative side, only when all the fixed points on the positive side of the \(y\)-axis are either saturated or oversaturated. Due to this movement, the configuration would transform into a balanced configuration. Next, case 3 would follow. **Case 3. **: \(C(t)\in\mathcal{I}_{2}\) is a balanced configuration and all the fixed points in one of the half-planes are either saturated or oversaturated. Notice that a candidate robot, selected by the execution of \(CandidateRSelection(C(t))\), would never lie on a saturated circle. As a result, once a circle becomes saturated, it would never become unsaturated. Thus, all the fixed points on the positive side of the \(y\)-axis would never become unsaturated. This implies that at any \(t^{\prime}>t\) the agreement on the positive direction of the \(x\)-axis remains invariant. **Case 4. **: \(C(t)\in\mathcal{I}_{2}\) is a balanced configuration with at least one unsaturated fixed point in both the half-planes. Furthermore, \(k\) is odd and \(F_{y}\
eq\emptyset\). In this case, the positive \(x\)-axis direction is considered towards the half-plane in which there has been more progress at time \(t\). During an execution of \(TargetFPSelection(C(t))\), the unsaturated fixed points with higher configuration rank are given preference over the unsaturated fixed points with lower configuration rank. As a result, it is guaranteed to have more progress in the positive side of the \(y\)-axis for any \(t^{\prime}>t\). Therefore, for any \(t^{\prime}>t\) the agreement on the positive direction of the \(x\)-axis remains invariant. In case \(t=0\), it might be possible that both the half-planes have the same progress.