Coating
Particles must cover a fixed object as uniformly as possible: in layers, each filled before the next.
Problem statement and measuresexpand
A fixed object (a connected set of nodes of the triangular lattice that particles cannot enter) is surrounded by particles. They must arrange themselves into layers around the object, each layer filled before the next. Time in rounds; work is the number of moves (expansions and contractions).
Measures: Time, asynchronous rounds; Moves, total expansions and contractions (work).
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
Moves
Universal coating + constant memory, + strong scheduler, + chirality, + randomized
0 open · 2 results
tight
\(O(n)\) vs \(\Omega(n)\)
locality
tight
\(O(n^2)\) vs \(\Omega(n^2)\)
distance
tight
\(O(n^2)\) vs \(\Omega(n^2)\)
oblivious silent particles
unknown
— vs —
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.