Voronoi Coverage

The clean answer was waiting in a math notebook from 1908, and a swarm of robots can rediscover it in about a dozen steps. Before we name it, let's watch it happen.

Watch the swarm find its fair shares

Below, each dot is a robot that "owns" the region of the field closest to it: its Voronoi cell. Every robot creeps toward the center of its own cell, the cells reshape, and the whole swarm settles into an even tiling. No leader, no central plan.

Try this:

1. Start crowded. Bunch the agent count up and hit play. Watch the dots shove each other apart, not by pushing, but by each one chasing the middle of its own shrinking territory.
2. Read the boundaries. Every wall between two cells is the line of points exactly equidistant from those two robots. That's the whole definition of a Voronoi diagram, drawn for free.
3. Block off a corner. Drop an obstacle and the cells deform around it. Robots re-center on the reachable part of their turf, and coverage repairs itself with zero replanning.
4. Let it converge. Step until the dots stop moving. That stillness is a centroidal Voronoi tessellation: every robot sitting at its own center of mass.

Two rules, run on a loop: figure out whose turf is whose, then walk to the middle of yours. That loop is Lloyd's algorithm, and it is gradient descent in disguise.

Whose turf is this?

A Voronoi diagram carves a space into cells (one per robot) by a single rule: a point belongs to whichever robot is nearest. That's it. The borders fall out automatically as the set of points that can't decide, the ones perfectly balanced between two neighbors.

$V_i = \{p : \|p - p_i\| \leq \|p - p_j\| \;\;\forall\, j \neq i\}$

Read it aloud: cell V_i is every point p that is at least as close to robot i as to any other robot j. The whole field gets partitioned, no point left unclaimed, no point claimed twice.

The name stuck to Voronoy, but he was late to the party. Descartes sketched the same nearest-point regions informally back in 1644, carving up the heavens into zones of influence around stars. Two centuries later Peter Gustav Lejeune Dirichlet used the cells in earnest, in 2D and 3D, while studying quadratic forms in 1850. That is why the same picture has two other honest names: the Dirichlet tessellation in math, and Thiessen polygons in weather (after the American meteorologist Alfred H. Thiessen, who in 1911 used them to spread scattered rain-gauge readings across a watershed). One shape, four labels, three centuries of people reinventing it.

The two-step that fixes the swarm

Knowing the cells isn't enough. A robot parked in the corner of a huge cell is doing a bad job of covering it. So each robot takes one step toward the centroid of its cell, the center of mass of its territory:

$c_i = \frac{\int_{V_i} p \, dp}{\int_{V_i} dp}$

Then everyone recomputes their cells, because moving changed the boundaries, and steps again. This is Lloyd's update, $p_i \leftarrow c_i$, looped to convergence. Each pass spreads the robots more evenly, and the swarm's worst-case coverage error (the farthest any point in the field is from its nearest robot)

$E = \max_{p \in \Omega} \min_i \|p - p_i\|$

drops monotonically until it can't drop anymore. No robot needs to know where the others are, only the edges of its own cell. Coordination without a coordinator.

↘ Why does walking to the centroid actually minimize coverage error?

Lloyd's algorithm isn't a heuristic that happens to work. It's gradient descent on a real cost function. Define the swarm's coverage cost as the total squared distance from every point in the region to its nearest robot, weighted by an importance density $\phi(p)$:

$\mathcal{H}(p_1,\dots,p_n) = \sum_{i=1}^{n} \int_{V_i} \|p - p_i\|^2 \, \phi(p)\, dp$

Take the gradient with respect to one robot's position. The cell boundaries shift as $p_i$ moves, but those boundary terms cancel (each border point is equidistant from two robots, so it contributes equally to both cells). What survives is clean:

$\frac{\partial \mathcal{H}}{\partial p_i} = 2 M_{V_i}\,(p_i - c_i)$

where $M_{V_i}$ is the mass of the cell and $c_i$ its centroid. The gradient is zero exactly when $p_i = c_i$, when every robot sits at its own centroid. That fixed point is the centroidal Voronoi tessellation, and stepping toward $c_i$ is literally stepping downhill on $\mathcal{H}$. Swap in a non-uniform $\phi(p)$ (say, "the western half matters twice as much") and the same loop crowds robots into the important regions automatically.

Where this shows up

• Search and rescue: drones partition a disaster zone so no patch goes unsearched and none gets double-covered.
• Precision agriculture: a fleet of ground robots splits a field into fair plots, each tending its own centroidal cell.
• Sensor networks: static motes adjust sensing focus so coverage is even: exactly the math, minus the wheels.
• Surveillance and monitoring: UAVs self-organize to watch a region with the fewest blind spots, re-tiling on the fly as one drops out.

The pattern is always the same: a job too big for any one agent, divided into fair shares that the agents negotiate purely by looking at their own backyard.

Key takeaways

• A Voronoi diagram splits space by nearest robot: every cell is one robot's turf, every border a line of equidistant points.
• Lloyd's algorithm is a two-step loop: compute cells, walk each robot to its cell's centroid, repeat.
• The loop is gradient descent on coverage cost, so error falls monotonically to a centroidal Voronoi tessellation.
• It's decentralized (each robot needs only its own cell, never the global map), which is why a swarm can run it forever.