Voronoi Diagrams

Voronoi Diagrams #

The plane cut into nearest-site regions.

A Voronoi diagram cuts the plane into the region of points nearest to each site

Here are two towns, A and B, on the plane. Which points are nearer to A than to B?

The points equally far from A and B make the perpendicular bisector of AB.

That bisector splits the plane in two, and every point on the A side is nearer to A.

With four towns, draw the bisector of every pair and keep, for each town, the piece where it is nearest.

Each piece is a cell: every point in it is nearer to that site than to any other.

A cell edge is a piece of a bisector, and a vertex is where three cells meet.

The Equation of a Voronoi Edge #

Midpoint, negative reciprocal, and out it comes.

A Voronoi edge is the perpendicular bisector of two sites, taken through their midpoint

Site A is at (1, 2) and site B is at (5, 4). Their boundary is the perpendicular bisector of AB.

The midpoint of AB averages the coordinates: $\left(\frac{\left(1+5\right)}{2},\frac{\left(2+4\right)}{2}\right)=\left(3,3\right)$((1 + 5)/2, (2 + 4)/2) = (3, 3).

The gradient of AB is $\left(4-2\right)÷\left(5-1\right)=\frac{1}{2}$(4 − 2) ÷ (5 − 1) = 1/2.

A perpendicular gradient is the negative reciprocal: $-1÷\frac{1}{2}=-2$−1 ÷ 1/2 = −2.

Through (3, 3) with gradient −2: y − 3 = −2(x − 3).

Rearranged, that is y = −2x + 9, and it is the edge between the two cells.

Finding the Nearest Site #

Which cell a point lands in, and what changes.

A point belongs to the cell of whichever site is nearest to it

The point P at (8, 4) lies inside the cell of C, so C is the nearest town to P.

Check it by measuring: the distance to C is the smallest of the four.

If each town records a measurement, such as rainfall, nearest-site interpolation gives P the value recorded at C.

Add a new town E: its cell is every point nearer to E than to any of the older towns.

The cell of E is cut from the neighboring cells, and each of its edges lies on the perpendicular bisector of E and one neighbor.

Adding a site only ever shrinks the cells around it; none of them can grow.

The Toxic Waste Dump Problem #

The largest empty circle sits at a vertex.

The point furthest from every site is at a Voronoi vertex or a corner of the region, at the center of the largest empty circle

A waste dump has to sit as far as possible from every town. Where should it go?

Inside a cell you can always step farther from the nearest town, so no point inside a cell can be the best.

At a Voronoi vertex three cells meet, and three towns are all equally near.

The circle through those three towns holds no town inside it: an empty circle.

The other vertex at (7, 7) gives a bigger empty circle, of radius exactly 5.

Test every vertex and keep the largest empty circle: its radius is the greatest distance the dump can have from the nearest town.

A corner of the region is a candidate too, so check the border as well as the vertices.

The Area of a Voronoi Cell #

Find the corners, then it is mensuration.

A Voronoi cell is a polygon, so its area comes from its corners by ordinary mensuration

The cell of A is a polygon, so it has an area like any other polygon.

Its corners are (0, 0), (6, 0), (6, 4), (4, 6) and (0, 6), read off the axes.

Two edges lie on the border of the region, and the other three are pieces of bisectors.

The cell sits inside a 6 by 6 square with one corner cut off by the edge it shares with the cell of D.

That slice is a triangle of area 2, so the cell covers 36 − 2 = 34 square units.

Adding another site would cut into this cell, so its area can only get smaller.