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›oblivious, weak scheduler, + chirality

SILBOT, chirality, deterministic

verified
Time: tightMoves: unknown

Silent oblivious particles with chirality coat a convex object with one layer, deterministically, in \(O(n^2)\) rounds.

Assumed (added on the last edge are outlined)

+Orientationcommon chirality

Not assumed

Memoryoblivious, silent particles (SILBOT)Schedulerweak: non-atomic activations, an action may interleave with othersRandomnessdeterministicInitial shapeconnected, holes allowedConnectivity during executionthe system must stay connected
Formal definitions of this setting
Memory: oblivious
No persistent state and no messages; a particle decides from its view only.
Scheduler: weak scheduler
An activation's look, compute and move need not be atomic; concurrent activations may interfere. The scheduler of Bazzi and Briones is described as weak sequential, as non-atomic, and as fair asynchronous by different later papers Briones et al. 2023 Dufoulon et al. 2021 Chalopin et al. 2026.
Orientation: chirality
All particles agree on clockwise order, not on a common direction.
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.

Statement for this variant

Single-layer coating of a convex object, together with compaction of holes.

What is known

Time · asynchronous rounds
tight
\(\Theta(n^2)\) rounds; the lower bound is argued informally.
lower bound
\(\Omega(n^2)\) Navarra & Piselli 2023
bottleneckoblivious silent particles
holds when
  • informal argument before Theorem 4, not a theorem
introductory—
current best
\(O(n^2)\)
2-hop viewexterior awareness: a particle can tell a hole from the outside
Moves · total expansions and contractions (work)
unknown
—
lower boundnone known
introductory—
current best—

Results, in order of publication

Navarra & Piselli 2023 current best
Time \(O(n^2)\)
2-hop viewexterior awareness: a particle can tell a hole from the outside

Introductory and current best.

Open questions

  1. Coating in SILBOT without chirality Navarra & Piselli 2023.

  2. Multi-layer coating, which "seems unfeasible" in SILBOT Navarra & Piselli 2023.

Notes

Checked against the full text.

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

No catalogued weaker setting.

Lower bounds from stronger settings hold here

Universal coating
Time \(\Omega(n)\)Moves \(\Omega(n^2)\)

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