# Uniform Circle Formation for Fully, Semi-, and Asynchronous Opaque Robots with Lights
## 5 The Algorithm for the Fully Synchronous Mode
### Cycle 1: Pivot Selection and Angle Setting  
From \(C_{H}\), the algorithm starts setting the regular tuples. The algorithmic dynamic depends on the degree of symmetry of \(C_{H}\). Three cases must be considered: _asymmetry_, _symmetry with exactly one axis_, and _rotational symmetry_. **Asymmetry. ** Consider the case of asymmetry, i.e., no symmetry axis exists in \(C_{H}\). However, there exists at least one diameter passing through a robot and dividing the SEC into two halves, upon which robots distribute according to Theorem 1. The robot swarm must agree on one such diameter, say \(D\), which will be the _main diameter_. To find \(D\), robots agree on starting from a commonly designated robot \(x\) and following a common orientation on the SEC. The following lemma is needed to perform this task:  
**Lemma 1**. : _Starting from the configuration \(C_{H}\) and in case of asymmetry, all robots on the SEC are able to unambiguously agree on a robot \(x\)._  
Proof. : Let \(r\) be any given robot on the SEC. It considers all possible \(2n\) SEC angle-strings, and unambiguously chooses one of them, e.g., the lexicographically smallest string, which starts from just one robot, given the asymmetry of \(C_{H}\). So, the robot \(x\) is the elected robot for any \(r\). So, let \(x\) and \(w\) be the robot and the lexicographically smallest angle-string chosen according to Lemma 1. This enables the algorithm to elect a _starting_ robot (i.e., \(x\)) and an _orientation_ on the SEC (i.e., the direction given by \(w\)), by which the main diameter \(D\) search can be carried on: each robot starts checking whether the diameter through \(x\) satisfies Theorem 1 and, if this is not the case, it tries with the next robot along the orientation settled by \(w\). Clearly, this process makes the whole swarm converge on the claimed main diameter \(D\). Let \(p\) be the position of the robot that determines \(D\). The strategy distinguishes between having an odd or even number \(n\) of robots in the swarm. Even \(n\). By Theorem 1, one or two robots may sit at the endpoints of \(D\). In both cases, the robot at position \(p\) assumes the color _pivot_. Moreover, in the second case, the opposite robot on \(D\) assumes the color _angle_. The explanation continues discussing the first situation, since the second may be easily derived. By Theorem 1, one of the half-SEC, say \(H^{+}\), has one more robot than the other, say \(H^{-}\). So, a robot in \(H^{+}\) needs to move to the empty endpoint \(a_{3}\) (opposite to \(p\)) of \(D\) and assume the color _angle_. At the same time, two other positions \(a_{1}\) and \(a_{2}\) (regular polygon vertices) must be reached by two robots. These two positions correspond to the polygon vertices at the immediate left and right of \(p\). The three robots sat at positions \(a_{1}\), \(p\), \(a_{2}\) form the _regular 3-tuple_ (see Figure 4). So, globally, three robots must be moved: two from \(H^{+}\) and one from \(H^{-}\), so that both the half-SECs contain the same number of robots at the end of this round. The orientation provided by \(x\) and \(w\) is used to determine which robots in \(H^{+}\) and \(H^{-}\) must move to the vertices of the polygon: for instance, the last robots by such an orientation can be selected. Then, Theorem 2 ensures that the three vertices will be safely reached by the robots. Summing up, each robot \(r\) performs the following:  
* **Look-Compute**: \(r\) unambiguously spots the pivot position \(p\) on the main diameter. Furthermore, it computes the positions \(a_{1}\), \(a_{2}\), \(a_{3}\) and the robots intended for these positions. * **Move**: If \(r\) is in the pivot position \(p\), then it does not move and sets its color as _pivot_. If \(r\) is intended for the position \(a_{1}\), \(a_{2}\), or \(a_{3}\), it sets its color as _angle_ and moves there. Otherwise, \(r\) does nothing. Odd \(n\). A single robot lies on the main diameter \(D\), specifically at one of its endpoints, say \(p\).