Mobility Matters
Home›Programmable matter›Self-organising particle systems›Convex hull formation

Convex hull formation

Particles must enclose an object in its convex hull, sensing only locally.

Problem statement and measurescollapse
LLLLLLLLLLStart: leader L, all six walls through itRole swap: the leader's role moves onA step beyond a wall pushes itAll six walls touched, none pushed: hull knownThe particle in the bay steps outFinal: every node next to the hull occupied
Convex hull formation, following Daymude et al. 2020: a leader (L) walks clockwise around the object (black) and keeps its distance to six walls, one per side of a hexagon with lattice-parallel sides; a step beyond a wall pushes that wall outwards (dashed: the current estimate). Here the particles already surround the object, so the leader advances by role swaps, handing its role and counters to the particle ahead, and nobody moves. Once the leader has touched all six walls since its last push, the hull is known, and the particle in the bay steps out (expansion, contraction), so that the particles occupy exactly the nodes that neighbour the hull.

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

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Imagine sealing an oddly shaped object inside the tightest convex 'fence', like a rubber band stretched around it. The floor is the triangular lattice: the endless graph whose nodes are the corners of a tiling of the plane by equal triangles; each node is joined by an edge to six others, its neighbours. A particle occupies one node and moves in two actions: an expansion into an empty neighbouring node, after which it occupies both, then a contraction into one of the two; so one expansion and one contraction move it by one node. A fixed object occupies a connected set of nodes that particles cannot enter, and particles sit next to it; \(B\) is the length of the object's boundary (the walk around its outside). The particles must occupy exactly the nodes of the object's convex hull, taken one layer outside the object: on the triangular lattice, the smallest region bounded by six straight sides in the lattice's three directions that contains the object. Particles have constant memory, no compass (no agreement on the six directions of the lattice), and an adversarial scheduler; one particle starts as the leader on the object's boundary. Time is counted in rounds (intervals of time in which every particle is activated at least once).

1AlgorithmWalk around the object and push six walls outwards No orientation → Daymude et al. 2020
  1. Using its own local names for the six directions, the leader imagines six walls (half-planes), one per side of the future hull. It keeps six counters: its distance to each wall, all starting at 0.
  2. The leader walks clockwise around the object's boundary. Each step brings it closer to two walls and farther from two others, and it updates the counters.
  3. If a step would take it beyond a wall (a counter already at 0 must go down), that wall is pushed one step outwards: the estimate of the hull grows.
  4. The leader also remembers, for each wall, whether it has touched that wall since its last push. Once it has touched all six without pushing any, the walls are in their final places.
  5. The counters can be as large as \(B\), too big for one particle, so the followers trailing the leader each store one bit of a binary counter.
  6. Finally the particles fill the nodes along the six walls.
Why it works and what it costs. The walls only move outwards and stop at the true hull, so the walk ends with the correct hull. The paper proves that the whole process, including the distributed counters, takes \(O(B)\) rounds Daymude et al. 2020. The same algorithm can be extended to a tighter hull (the weak \(\mathcal{O}_\Delta\)-hull) in the same time; if there are too few particles, it forms as much of the hull as it can.

Why it matters. Distributed binary counters let constant-memory particles count up to large numbers, a tool other algorithms reuse.

2Lower boundSomeone must reach the far end No orientation →

This simple argument is ours; the catalogue records no lower bound for this problem. Let the object be a long straight bar, so \(B\) is about twice its length, and let all the particles start bunched together near one end, enough of them to fill the hull. The hull has nodes next to the far end of the bar, at distance about \(B/2\) from where the particles start, so some particle must travel about \(B/2\) nodes.

Why it holds. Each node of travel takes one expansion and one contraction, and an unkind scheduler may let each particle act only once per round, so this takes at least about \(B/2\) rounds. So \(\Omega(B)\) rounds are needed in the worst case, and the \(O(B)\) algorithm above is best possible on such inputs.

Why it matters. It shows that the boundary length, not the number of particles, is the right measure for this problem.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Time
Moves
No orientation standard
\(O(B)\) rounds without shared orientation.
unknown \(O(B)\) vs —
unknown — vs —

What the community started looking at

Convex hull formation asked whether particles without shared orientation can compute a global geometric property, and how fast Daymude et al. 2020.

All settings

The assumption tree (1 settings, 1 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time, Moves); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Memory › Scheduler › Orientation › Randomness › Initial shape › Connectivity during execution.

tight near-optimal polynomial gap unknown impossible no variant

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