# \(k\)-Circle Formation and \(k\)-epf by Asynchronous Robots
## 4 Algorithm
### Moveto Destination
If a candidate robot has to pass through a saturated circle in order to reach the circle centered at its target fixed point, then it would reach the circle in at most three epochs. This is because the movement path would intersect the saturated circle either one or two times. From the above two observations, it follows that a candidate robot would reach the circle centered at its target fixed point within \(2(m-1)+1=2m-1\) epochs. This is because, it might have to pass through \((m-1)\) number of saturated circles. Since \(AlgorithmOneAxis\) is sequential, each target fixed point would need at most \(k(2m-1)\) epochs to become saturated. Therefore, the \(k\)-circle formation problem would be solved within \(\mathcal{O}(m^{2}k)\) epochs. This is a loose upper bound on the running time of \(AlgorithmOneAxis\) in terms of epochs. ## 6 Relationship between the k-Circle Formation Problem and the k-epf Problem

Given \(m>0\) fixed points and \(n=\mathrm{km}\) robots for some positive integer \(k\), the \(k\)-epf problem asks exactly \(k\) robots to reach and remain in each fixed point. Since the definition of the \(k\)-circle formation problem asks for distinct robot positions, we only consider the initial configurations with distinct robot positions. We want to prove the following theorem. Theorem 6.1: _For a given initial configuration with distinct robot positions and a positive integer \(k\), if the \(k\)-circle formation problem is deterministically solvable then the \(k\)-epf problem is also deterministically solvable._

In order to prove the above theorem, we modify the proposed algorithm \(AlgorithmOneAxis\), to solve the \(k\)-epf problem deterministically within finite time. Algorithm for the k-epf Problem

Let \(C(0)\) be the given initial configuration. Suppose the \(k\)-circle formation problem has been solved in \(C(t)\), for some \(t\geq 0\), with radius \(\rho\), by the execution of \(AlgorithmOneAxis\). In order to solve the \(k\)-epf problem, the robots must reach the fixed points. The robots can accomplish this by moving in a straight line towards the fixed point. Since the robots are oblivious, they do not remember any information about the past events. Therefore, if any robot stops before reaching the fixed point for some \(t^{\prime}>t\), it would not remember that the \(k\)-circle formation problem has already been solved. As a result, it will again start executingAlgorithmOneAxisIn order to resolve such a situation, consider the following definition. A configuration is said to satisfy Property 1, if the following conditions hold:

1. Each robot lies within \(\rho\) distance from some fixed point. 2. For each \(f_{i}\in F\), there are at most \(k\) robots, which lie within \(\rho\) distance from \(f_{i}\). Given a configuration which satisfies Property 1, let \(\mathcal{A}\) be an algorithm as follows:

1. If there exists a robot \(r_{i}\) such that \(0<d(r_{i},f_{j})\leq\rho\) for some \(f_{j}\in F\), then \(r_{i}\) moves along \(\overline{r_{i}f_{j}}\) towards \(f_{j}\). Define algorithm \(Algokepf\) as follows:

1. If the current configuration satisfies Property 1, then execute \(\mathcal{A}\). 2. Else the robots execute \(AlgorithmOneAxis\). During an execution of \(\mathcal{A}\), it must be ensured that none of the robots have any inherent motion, which is not directed towards the fixed point. Since all the robots are stationary in the initial configuration, if \(C(0)\) satisfies Property 1, then none of the robots would have any inherent motion. Lemma 10: _During an execution of \(AlgorithmOneAxis\) if \(t>0\) is the earliest possible point of time at which the configuration \(C(t)\) satisfies Property 1, then none of the robots would have any inherent motion in \(C(t)\)._

Proof of Lemma 10: Since \(C(t)\) satisfies Property 1, each robot lies within \(\rho\) distance from some fixed point. Furthermore, notice that there are no oversaturated circles in \(C(t)\). Let \(f_{j}\) be the target fixed point which became saturated at time \(t\) due to the movement of a candidate robot (say \(r_{i}\)).