Mutual visibility
Opaque robots must reach positions where no three are collinear, so that every robot sees every other.
Problem statement and measuresexpand
\(n\) opaque point robots (or unit discs) start at distinct points: a robot hides the robots behind it on the same line of sight. They must reach a configuration in which every robot sees every other (no three collinear), without collisions.
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
\(3\) vs \(2\)
memory
tight
\(\text{finite}\) vs —
tight
\(2\) vs \(2\)
memory
tight
\(O(1)\) vs \(\Omega(1)\)
trivial
tight
\(47\) vs \(2\)
memory
unknown
\(\text{finite}\) vs —
tight
\(3\) vs \(2\)
memory
unknown
\(O(\log n)\) vs —
tight
\(12\) vs —
Lights, one crash, SSYNC, rigid, compass + crash faults, + SSYNC, + lights (LUMI), + compass, + rigid
1 open · 1 results
unknown
\(\text{finite}\) vs —
tight
\(3\) vs —
Lights, one Byzantine robot Byzantine, + SSYNC, + lights (LUMI), + compass, + rigid
0 open · 0 results
impossible
— vs \(\text{impossible}\)
indistinguishable Byzantine agents
impossible
— vs —
unknown
\(O(n)\) vs —
tight
\(O(1)\) vs —
unknown
\(O(n)\) vs —
tight
\(2\) vs \(2\)
memory
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.