Convex hull formation
Particles must enclose an object in its convex hull, sensing only locally.
Problem statement and measuresexpand
Particles must form the convex hull (and the weak \(\mathcal{O}_\Delta\)-hull) of a fixed object, a connected set of nodes of the triangular lattice that particles cannot enter. \(B\) is the length of the object's boundary.
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
unknown
\(O(B)\) vs —
unknown
— vs —
Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.