Mobility Matters
Home›Programmable matter›Self-organising particle systems›Coating

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).

no assumptions›+ constant memory, + strong scheduler, + chirality, + randomized

Universal coating

standard settingverified
Time: tightMoves: tight

Any object admitting a uniform coating is coated with optimal work, and in \(\Theta(n)\) rounds with high probability.

Assumed (added on the last edge are outlined)

+Memoryconstant memory and local communication+Schedulerstrong: atomic activations under a fair adversary+Orientationcommon chirality+Randomnessrandomized

Not assumed

Initial 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: chirality
All particles agree on clockwise order, not on a common direction.
Randomness: randomized
Particles flip fair coins; guarantees hold with high probability or in expectation.
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
tight
\(\Theta(n)\) rounds.
lower bound
\(\Omega(n)\) Daymude et al. 2018
bottlenecklocality
holds when
  • Lemma 1: deterministic worst case
  • a line of \(n\) particles attached to the object by one particle, the object's boundary longer than \(n\)
introductory—
current best
\(O(n)\)
Moves · total expansions and contractions (work)
tight
\(\Theta(n^2)\) moves.
lower bound
\(\Omega(n^2)\) Derakhshandeh et al. 2017
bottleneckdistance
holds when
  • Lemma 15
introductory
\(O(n^2)\)
current best
\(O(n^2)\)

Results, in order of publication

Derakhshandeh et al. 2017 introductory
Moves \(O(n^2)\)

Worst-case work-optimal: \(\Theta(n^2)\) moves (Theorem 2).

Daymude et al. 2018 current best
Time \(O(n)\)

With high probability; randomisation enters only through the leader election.

Open questions

None recorded for this variant.

Notes

Chirality is part of the model of both papers. In 3D hybrid programmable matter (one finite-automaton agent moving passive tiles), universal coating takes \(O(n^2)\) steps, worst-case optimal against an agent with global knowledge Kostitsyna et al. 2024. Checked against the full texts.

What carries over from neighbouring settings

Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.

Algorithms from weaker settings work here

SILBOT, chirality, deterministic
Time \(O(n^2)\)

Lower bounds from stronger settings hold here

No catalogued stronger setting.

Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.