3.6 Voronoi diagramsIB Maths: Applications and Interpretation SL: Revision notes

A Voronoi diagram divides a plane into regions according to which of a set of points is closest.

• The given points are sites (schools, weather stations, hospitals).
• Each cell is the region of points closer to its site than to any other site.
• An edge is a boundary between two cells: points equidistant from two sites, part of the perpendicular bisector of the sites.
• A vertex is where edges meet. In exam questions, a vertex is always where three edges meet. It is equidistant from three sites.

In examinations the coordinates of the sites are given, and you are not asked to construct bisectors. You may be asked for the equation of a boundary: find the perpendicular bisector of the two sites.

1. Midpoint of the two sites.
2. Gradient of the line joining them; take the negative reciprocal.
3. $y-y_1=m(x-x_1)$. Example: sites $A(2,1)$ and $C(6,9)$. Midpoint $(4,5)$, gradient of $AC$ is $2$, so the edge has gradient $-\frac12$: $y=-\frac12x+7$. Sites with equal $y$-coordinates give a vertical edge (e.g. $A(2,1)$, $B(10,1)$: $x=6$). A vertex is found by solving two edge equations simultaneously, e.g. $x=6$ and $y=-\frac12x+7$ give $(6,4)$.

To decide which site is closest to a point $X$, calculate the distance (or squared distance) from $X$ to each site and choose the smallest. Using squared distances avoids square roots. Example: sites $P(1,2)$, $Q(7,2)$, $R(4,8)$ and $X(5,3)$. Squared distances: $XP^2=17$, $XQ^2=5$, $XR^2=26$. The closest site is $Q$, so $X$ lies in the cell of $Q$. A point on an edge is equidistant from two sites; it belongs to both cells.

When a new site is added, a new cell appears around it. Its edges are the perpendicular bisectors between the new site and its neighbouring sites. Parts of the old cells are taken over by the new one, so the neighbouring cells shrink and edges and vertices change. Cells of sites far from the new one may be unaffected. Example: stations $R_1(3,3)$, $R_2(9,3)$ with edge $x=6$. A new station $R_3(6,7)$ creates edges $y=-0.75x+8.375$ (with $R_1$) and $y=0.75x-0.625$ (with $R_2$), meeting $x=6$ at the vertex $(6,3.875)$. The edge $x=6$ now only exists below this vertex.

Cells are polygons, so find coordinates of the vertices and split the region into triangles or rectangles. Example: the reserve is $0\le x\le12$, $0\le y\le8$. The cell of $R_3$ has vertices $(6,3.875)$, $(0.5,8)$ and $(11.5,8)$ (the last two are where the edges meet $y=8$). It is a triangle with base $11$ and height $4.125$, so area $=\frac12(11)(4.125)=22.7$ km$^2$, which is $\frac{22.69}{96}=23.6\%$ of the reserve. Substitute the boundary value (here $y=8$) into an edge equation to find where an edge meets the side of the region.

Nearest neighbour interpolation estimates a value at a point using the value at the closest site: every point in a cell is given the same value as its site (for example rainfall). Example: $X(5,3)$ is in the cell of $Q$, so the rainfall is estimated as $Q$'s reading, 80 mm. It is not the mean of the readings. Toxic waste dump problem: to place a facility as far as possible from its nearest site (a waste dump, a noisy factory), choose a vertex of the Voronoi diagram. Vertices are the points furthest from their three closest sites. Find the vertex by solving two edge equations, then the distance from the vertex to a site. Example: villages $V_1(0,0)$, $V_2(8,0)$, $V_3(2,6)$ have a vertex at $(4,2)$, which is $\sqrt{20}=4.47$ km from each village. Other contexts: urban planning, spread of diseases, ecology, meteorology and resource management.