# Uniform Circle Formation for Fully, Semi-, and Asynchronous Opaque Robots with Lights
## 3 Some Notions and Results  
Consider a swarm of \(n\) robots and assume all of them sit on their _smallest enclosing circle_ (SEC). Two distinct robots \(p,q\) on the SEC delimit two arcs \(\widehat{pq}\) (clockwise and counterclockwise); \(p\) and \(q\) are _adjacent_ whenever there is at least one of the two arcs \(\widehat{pq}\) upon which no other robot sits. Clearly, in a robot swarm forming a regular \(n\)-gon, each pair \(p,q\) of adjacent robots forms an angle \(\frac{2\pi}{n}\) with the center \(O\) of the SEC, formally \(\widehat{pOq}=\frac{2\pi}{n}\). Such an angle will be called the _base angle_ of the \(n\)-gon. Let \(Colors\) be the set of the possible colors, where each color is represented by a string. Along the paper, the following name convention will be used: any given robot whose light color is a string with prefix _pivot_ or _angle_ is called a pivot or an angle robot, respectively. Pivot and angle robots will be set to fix the base angle, and some strategic segments within the SEC; the other robots will use these strategic segments to reach their own target positions. According to this, the following definitions are now given:  
**Definition 1**. : _For \(2\leq k\leq n\), let \((r_{1},r_{2},\ldots,r_{k})\) be a \(k\)-tuple of distinct robots on the SEC (centered on \(O\)). Such a tuple is called a regular \(k\)-tuple if it satisfies the following conditions:_  
* \(r_{\widehat{i}}\widehat{O_{i+1}}=\frac{2\pi}{n}\) _for every_ \(1\leq i<k\)_;_
* \(r_{i}\) _is a pivot or angle robot for every_ \(1\leq i\leq k\)_;_
* _For odd_ \(k\)_, just the central robot_ \(r_{\widehat{\lfloor}\frac{k}{2}\rceil}\) _can be a pivot;_
* _For even_ \(k>2\)_, just the two central robots_ \(r_{\frac{k}{2}}\)_,_ \(r_{\frac{k}{2}+1}\) _can be pivots simultaneously._  
The strategies to move the robots on the vertices of a regular \(n\)-gon (inscribed in the SEC) start by setting particular regular \(\{2,3,4,5\}\)-tuples. These tuples will not move for the whole computation, while the other robots will move to complete the regular \(n\)-gon. From now on, unless otherwise stated, given two points \(a,b\) on the SEC, the arc \(\widehat{ab}\) refers to the _minor arc_ joining \(a\) and \(b\) on the SEC. **Definition 2**. : _Let \(r_{1}\) and \(r_{2}\) be two robots on the SEC, and let \(d_{1}\) and \(d_{2}\) be the opposite endpoints of the diameters passing through \(r_{1}\) and \(r_{2}\), respectively. The overlap arcs for \(r_{1}\) and \(r_{2}\) are the arcs \(r_{1}d_{2}\) and \(r_{2}d_{1}\) (see Figure 1)._  
Clearly, if \(r_{1}\) and \(r_{2}\) sit on the endpoints of the same diameter, their overlap arcs have null length. **Theorem 1**. : _Let \(n\) be the number of robots lying on the SEC._  
* _For_ odd__\(n\)_, there exists a diameter passing through a robot and dividing the SEC into two halves, each having_ \(\frac{n-1}{2}\) _robots._
* _For_ even__\(n\)_, there exists a diameter dividing the SEC into two halves such that_ \((i)\) _either the diameter passes through just one robot and the half-SECs have_ \(\frac{n}{2}\) _and_ \(\frac{n}{2}-1\) _robots, or_ \((ii)\) _the diameter passes through two (opposite) robots and the half-SECs have_ \(\frac{n}{2}-1\) _robots each._  
Proof. : Consider an _odd__\(n\)_, and reason by induction on_ \(n\)_. For_ \(n=1\)_, the property follows straightforwardly. Now, assume the property holds true for an odd_ \(n>1\)_, and let us prove the property for_ \(n+2\)_. Let us rule out two robots, say_ \(r_{1}\) _and_ \(r_{2}\)_, having minimal overlap arcs_ \(\widehat{a}\) _and_ \(\widehat{a^{\prime}}\)_, so that_ \(n\) _robots are left on the SEC. So, by the induction hypothesis, there exists a diameter_ \(D\) _passing through a robot and dividing the SEC into two halves, each having_ \(\frac{n-1}{2}\) _robots. Notice that, by Definition 2, no robot can sit on_ \(\widehat{a}\) _and_ \(\widehat{a^{\prime}}\)_, and since_ \(D\) _passes through a robot, it clearly cannot leave_ \(r_{1}\) _and_ \(r_{2}\) _on the same half-SEC. Whence, the result follows.