Mobility Matters
Home›Mobile robots in the plane›Formation problems›Pattern formation›Uniform circle formation

Uniform circle formation

Robots must form a regular \(n\)-gon: a circle with equal spacing.

Problem statement and measurescollapse
Start: inner robots move out to the fixed circleAll on the circle: move to hexagon verticesFinal: a regular hexagon
Uniform circle formation: \(n\) oblivious robots at distinct points must occupy the vertices of a regular \(n\)-gon, of any position and size, and stay there Flocchini et al. 2017. Shown in SSYNC rounds (ringed robots are activated), simplified from Flocchini et al. 2017: the smallest enclosing circle (dashed) never changes; robots inside move out to it, then robots on it move to the vertices of a regular hexagon inscribed in it (hollow).

\(n\) robots start at distinct points and must reach the vertices of a regular \(n\)-gon (in any position and size) and stay there. Time is in epochs (ASYNC: intervals in which every robot completes at least one full Look–Compute–Move cycle) or rounds; colours count light colours in the luminous model.

Measures: Time, rounds (FSYNC, SSYNC) or epochs (ASYNC) until the task is done; "finite" when only solvability is known; Colours, colours of the light per robot (0 for oblivious robots).

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Picture guards who must stand evenly spaced around a circular fence that nobody has built: the circle and the spacing must come from the guards themselves. There are \(n\) robots, points at distinct places in the plane; their positions form the configuration. Each robot repeats a Look–Compute–Move cycle: it takes a snapshot of where the other robots are (Look), decides on a destination point (Compute) and moves towards it (Move). They are identical, silent, oblivious (no memory between cycles), and each uses its own local coordinate system, so they agree on no direction and no handedness. The scheduler (an adversary) decides the activation of robots, that is, when each performs a cycle, and is ASYNC: each phase may take any finite time. Every move is a non-rigid move: a robot may be stopped after a minimum distance \(\delta\). The robots must reach the vertices of a regular \(n\)-gon (a polygon with \(n\) equal sides and equal angles), one robot on each vertex, of any size and position, and stay there.

1AlgorithmFix the smallest enclosing circle, reach it, then let symmetric robots move as one ASYNC, oblivious, disoriented → Flocchini et al. 2017
  1. Compute the smallest enclosing circle (SEC) of all robots; every robot computes the same circle. All moves are chosen so that this circle does not change.
  2. Robots inside the circle move out to it, as in circle formation.
  3. With all robots on the circle, group them into analogy classes: two robots are analogous if some symmetry of the whole configuration maps one to the other.
  4. The scheduler could make analogous robots act identically anyway, so the algorithm makes each class always move together, deliberately and symmetrically.
  5. The robots compute the vertices of a regular \(n\)-gon on the circle and move to them class by class. Special configurations that are already close to regular (pre-regular, biangular) get their own procedure.
Why it works and what it costs. The overall plan is simple; the difficulty is that asynchronous robots act on outdated snapshots, so the analogy classes and destinations that one robot computes may already be stale. Flocchini, Prencipe, Santoro and Viglietta show that oblivious, disoriented robots with non-rigid moves form a regular \(n\)-gon in ASYNC from every initial configuration at distinct points, for every \(n\) Flocchini et al. 2017; the case \(n = 4\) is solved in Mamino & Viglietta 2016. Time is not analysed; for opaque robots with lights, \(O(1)\) epochs and \(O(1)\) colours suffice Feletti et al. 2026a.

Why it matters. It closed a long-standing question and showed that, for pattern formation, asynchrony, chirality and rigid moves do not add computational power.

2ImpossibilityTwo robots on the same point can never be separated ASYNC, oblivious, disoriented → Flocchini et al. 2017

Suppose two robots start at the same point. They get exactly the same snapshot. The adversary gives them identical local coordinate systems and the scheduler always activates them together. Identical robots with identical snapshots and identical local coordinate systems compute the same destination, so they move together and are still on one point after every cycle. A regular \(n\)-gon has \(n\) distinct vertices, so it is never formed.

Why it holds. This is why the problem asks for distinct starting points; Flocchini et al. note that with two robots on one point the problem is "easily seen to be unsolvable" Flocchini et al. 2017. The same trap is the reason careful algorithms never let two robots meet while they move.

Why it matters. It is the simplest example of a symmetry that oblivious deterministic robots can never break.

3ImpossibilityWhy only the point and the regular polygon can be formed from every initial configuration ASYNC, oblivious, disoriented → Suzuki & Yamashita 1999

Start the robots on a regular \(n\)-gon. Give every robot a local coordinate system whose \(x\)-axis points to the centre, all with the same unit. All robots get the same snapshot; if the scheduler activates all of them together, they all make the same move up to rotation, so the configuration stays a regular \(n\)-gon (or collapses to its centre). So from this initial configuration the only formable patterns are the regular \(n\)-gon and the single point.

Why it holds. Suzuki and Yamashita showed that the patterns formable from an initial configuration depend on its symmetricity, its amount of rotational symmetry Suzuki & Yamashita 1999; the regular \(n\)-gon has the most. Hence the point (gathering) and the regular \(n\)-gon (uniform circle) are the only patterns that might be formable from every initial configuration, and both are Flocchini et al. 2017.

Why it matters. It explains why the uniform circle is singled out among all patterns: it is one of only two universally formable ones.

Simulator watch an algorithm run

A simulator of Look–Compute–Move robots in the plane that runs in the browser. Each case below starts one of its algorithms from a fixed starting configuration and seed; the run is the simulator's, not a proof. Source.

Spread evenly on a circle. The simulator's uniform circle formation algorithm with 12 robots under its asynchronous scheduler. Open in the simulator ↗

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Time
Colours
ASYNC, oblivious, disoriented standard
Oblivious, disoriented, non-rigid robots form a regular \(n\)-gon from any configuration of distinct points, for every \(n\).
unknown \(\text{finite}\) vs \(\text{impossible}\) symmetry
tight \(0\) vs —
SSYNC, oblivious
The first deterministic uniform circle formation, for \(n \ge 5\) semi-synchronous robots.
unknown \(\text{finite}\) vs —
tight \(0\) vs —
Opaque robots with lights, ASYNC
With lights, opaque robots form a uniform circle in \(O(1)\) epochs with \(O(1)\) colours, which is optimal in both.
tight \(O(1)\) vs \(\Omega(1)\) trivial
tight \(O(1)\) vs \(\Omega(1)\) trivial
Opaque robots with lights, FSYNC
In FSYNC, opaque luminous robots form a uniform circle in 3 cycles with \(O(1)\) colours.
tight \(3\) vs —
tight \(O(1)\) vs —
Transparent fat robots, SSYNC
Transparent fat robots that agree on one axis form a regular \(n\)-gon of given side in SSYNC.
unknown \(\text{finite}\) vs —
tight \(0\) vs —
Opaque fat robots, ASYNC, limited visibility, compass
Opaque fat robots with limited visibility and a common coordinate system form a uniform circle of given centre and radius in ASYNC.
unknown \(\text{finite}\) vs —
tight \(0\) vs —

Open questions 3

ASYNC, oblivious, disoriented

  1. Can oblivious robots without lights form a uniform circle in \(O(1)\) epochs, with rigid or non-rigid moves? Feletti et al. 2026a

Opaque robots with lights, ASYNC

  1. What is the exact minimum number of colours for \(O(1)\)-epoch uniform circle formation in ASYNC? Feletti et al. 2026a
  2. Uniform circle formation with non-rigid moves in the luminous opaque model Feletti et al. 2026a.

What the community started looking at

Uniform circle formation was first asked as solvability: can disoriented oblivious robots form a regular polygon? It was solved for SSYNC Dieudonné et al. 2008 and then for ASYNC without chirality or rigidity Flocchini et al. 2017 Mamino & Viglietta 2016. Only after feasibility was settled did the community turn to time and colours for luminous opaque robots Feletti et al. 2023b Pattanayak & Sharma 2024, reaching \(O(1)\) epochs with \(O(1)\) colours Feletti et al. 2026a.

Special case of Pattern formation

Uniform circle formation is "an important special case of the geometric pattern formation problem" Feletti et al. 2026a: the target is the regular \(n\)-gon. It is also the special case of circle formation with equal spacing; circle formation is "its precursor" Feletti et al. 2026a.

Related problems

Circle formation: A uniform circle is a circle, so every uniform-circle algorithm forms a circle.

Perspectives

  • Weak robots in the plane Why the theory of robots in the plane starts from oblivious, anonymous, disoriented points; how formation problems became its testbed and the scheduler its adversary; and how a light with a few colours turned into memory, communication and a measure.

Further reading

Papers on this problem that are not yet placed in a setting.

  • Maiti et al. 2026b Min-Max Uniform Circle Formation by Asynchronous Mobile Robots. Min-max uniform circle formation: every robot is given a circle that encloses all robots, and the robots, starting at distinct points strictly inside it, must occupy the vertices of a regular \(n\)-gon inscribed in that circle so that the largest distance travelled by any robot is as small as possible. Without agreement on axes or chirality the robots cannot agree on an optimal assignment of robots to vertices (Theorem 1); the authors also claim impossibility under FSYNC with non-rigid moves without axis agreement even with chirality and lights (Theorem 2, an informal argument that a constant number of colours cannot store the optimal value) and without lights even with a common compass (Theorem 3). For ASYNC robots with non-rigid moves, agreement on one axis and lights of six colours, an algorithm moves each robot along a straight segment to its vertex in an optimal assignment, computed with the centralised algorithms of Bhattacharya et al. and of Chen et al., without collisions and with the optimal largest distance (Theorems 4, 5). The abstract also announces min-max circle formation without equal spacing; the text treats only the uniform case. Read (arXiv v1).
  • Biswas et al. 2023 Multiple Uniform Circle Formation by Fat Robots Under Limited Visibility. Several uniform circles at once: fat robots with limited visibility, a global coordinate system, memory and messages to avoid collisions, under a synchronous scheduler, compute the positions to occupy and form several uniform circles; the authors note that the method forms any shape whose points the robots can compute. A short paper with a correctness argument and simulations. Read in full.

All settings

The assumption tree (6 settings, 3 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time, Colours); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Body › Visibility › Opacity › Faults › Scheduler › Lights (persistent memory) › Agreement on coordinates › Movement › Multiplicity detection › Randomness › Identifiers.

tight near-optimal polynomial gap unknown impossible no variant

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.