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).
No orientation
standard settingverifiedTime: unknownMoves: unknown
\(O(B)\) rounds without shared orientation.
Assumed (added on the last edge are outlined)
+Memoryconstant memory and local communication+Schedulerstrong: atomic activations under a fair adversary
Not assumed
Orientationno common orientation and no chiralityRandomnessdeterministicInitial shapeconnected, holes allowedConnectivity during executionthe system must stay connected
Formal definitions of this setting
- Memory: constant memory
- Each particle has \(O(1)\) bits of persistent memory and reads or writes neighbours' memory.
- Scheduler: strong scheduler
- Each activation is executed atomically; the adversary chooses the order, fairly.
- Orientation: no orientation
- Each particle labels its six incident directions in its own clockwise or counter-clockwise order, starting anywhere.
- Randomness: deterministic
- No random choices.
- Initial shape: holes allowed
- The initial set of occupied nodes induces a connected subgraph; it may enclose empty regions.
- Connectivity during execution: stays connected
- At every time the occupied nodes induce a connected subgraph.
What is known
Time · asynchronous rounds
unknown
No lower bound found.
Moves · total expansions and contractions (work)
unknown
—
lower boundnone known
introductory—
current best—
Results, in order of publication
Daymude et al. 2020 current best
Time \(O(B)\)
Introductory and current best; uses distributed binary counters.
Open questions
None recorded for this variant.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.