Circle formation
Robots must reach positions on a common circle.
Problem statement and measuresexpand
\(n\) robots start at distinct points and must reach a configuration in which all of them lie on one circle, at distinct points, and stay there. Uniform circle formation additionally asks for a regular \(n\)-gon.
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).
Progress map
tight near-optimal polynomial gap unknown impossible· rows follow the assumption tree; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Time
Colours
unknown
\(\text{finite}\) vs —
tight
\(0\) vs —
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.