# \(k\)-Circle Formation and \(k\)-epf by Asynchronous Robots
## 2 Model and Definitions  
The robots are assumed to be dimensionless, oblivious, anonymous, autonomous, and homogeneous. They are represented by points in the Euclidean plane. They have unlimited visibility range and have no explicit way of communication. The movements of robots are non-rigid. The state of a robot can be either active or inactive. They execute Look-Compute-Move (LCM) cycle when they become active. We have considered a fair ASYNC scheduler, i.e., each robot is activated infinitely often and the duration of each LCM cycle is finite but unbounded. The robots have one axis agreement, i.e., they agree on the direction and orientation of any one of the axes. We assume that they have an agreement on the \(y\)-axis. The following notations have been used in the proposed algorithms. * **Configuration:** Let \(R=\{r_{1},r_{2},\ldots,r_{n}\}\) be the set of robots. Let \(r_{i}(t)\) denote the position of the robot \(r_{i}\) at time \(t\). \(R(t)=\{r_{1}(t),r_{2}(t),...,r_{n}(t)\}\) is the set of robot positions at time \(t\). We are given a set of fixed points denoted by \(F=\{f_{1},f_{2},\ldots,f_{m}\}\). It is assumed that \(n=\text{km}\) for some positive integer \(k\). Let \(c\) be the center of gravity of the set of fixed points \(F\). We assume that the \(y\)-axis passes through \(c\). We also assume that \(c\) is the origin. Let \(F_{y}\) and \(R_{y}(t)\) denote the set of fixed points and robot positions, respectively, on the \(y\)-axis at time \(t\). Let \(d(r,f)\) denote the Euclidean distance between \(r\) and \(f\). The pair \(C(t)=(R(t),F)\) represents the configuration at time \(t\). In an initial configuration \(C(0)\), it is assumed that all the robots are stationary and are placed at distinct positions. A configuration is said to be balanced at time \(t\) if the number of robots in both the open half-planes delimited by the \(y\)-axis is equal. Otherwise, the configuration is said to be unbalanced. * **Circles and radii of circles:** We consider that all the circles formed by the robots would have the same radius. Let \(\rho\) denote the radius of the circles. Furthermore, let \(C(f,\rho)\) denote the circle centered at \(f\in F\) with radius \(\rho\). We have used the following notations to formulate the radius \(\rho\) of the circles: 1. \(\rho_{1}=\) minimum distance between two fixed points. 2. \(\rho_{2}=\) minimum distance between a fixed point \(f\in(F\setminus F_{y})\) and the \(y\)-axis. The radius \(\rho\) is defined as \(\rho=\dfrac{1}{3}\min(\rho_{1},\rho_{2})\). * We call a configuration \(C(t)\) final if the following conditions hold: 1. Every robot \(r_{i}\) is on a circle \(C(f_{j},\rho)\) for some \(f_{j}\in F\), 2. \(C(f_{i},\rho)\cap C(f_{j},\rho)=\emptyset\) for \(f_{i}\
eq f_{j}\), 3. Each circle contains exactly \(k\) robots at distinct positions. The \(k\)-circle formation problem asks the robots to reach and remain in the final configuration, starting from an initial configuration. * A fixed point and its respective circle \(C(f_{j},\rho)\) are said to be unsaturated, if \(C(f_{j},\rho)\) contains less than \(k\) robots on it. Let \(N_{j}(t)\) denote the deficit in the number of robots in order to have exactly \(k\) robots on the \(C(f_{j},\rho)\). A fixed point and its respective circle \(C(f_{j},\rho)\) are said to be saturated, if \(C(f_{j},\rho)\) contains exactly \(k\) robots on it. In case \(C(f_{j},\rho)\) contains more than \(k\) robots, then \(C(f_{j},\rho)\) and \(f_{j}\) are called oversaturated. * **Configuration Rank. *
* Let \(y(s_{i})\) denote the \(y\)-coordinate of a point \(s_{i}\). Note that the robots do not have an agreement on the positive direction of the \(x\)-axis. In case, the robots could have an agreement on the positive direction of the \(x\)-axis, \(\beta(s_{i})\) denotes the \(x\)-coordinate of \(s_{i}\). Otherwise, \(\beta(s_{i})\) denotes the distance of \(s_{i}\) from the \(y\)-axis. The pair \(\gamma(s_{i})=(\beta(s_{i}),y(s_{i}))\) is the configuration rank of the point \(s_{i}\).