Revise Voronoi diagrams and nearest-neighbour problems for IB Mathematics: Applications and Interpretation (3.4)

A Voronoi diagram begins with a set of fixed points called sites, for example the locations of hospitals, schools or phone masts. From them the plane is split into cells, one per site. The cell of a site $P$ contains every point that is closer to $P$ than to any other site, so if you are standing somewhere in $P$'s cell then $P$ is your nearest site. The borders between cells are edges, and the corners where edges meet are vertices. Everything about the diagram flows from one idea: each feature is defined by distance to the sites.

It is worth pausing on why an edge is a perpendicular bisector. An edge separates the cell of $A$ from the cell of $B$, so it is made of exactly those points that are equally close to $A$ and to $B$. The set of all points equidistant from two fixed points is precisely the perpendicular bisector of the segment joining them. That single fact, equidistant from two points equals perpendicular bisector, is the engine behind every construction in this topic.

To construct a Voronoi diagram by hand you draw the perpendicular bisector of each pair of neighbouring sites and keep only the parts that genuinely form borders. For two sites there is a single dividing line. For three sites you draw three perpendicular bisectors; they meet at one vertex, and the three edges radiating from it split the plane into three cells. Adding more sites simply repeats the idea: bisect neighbouring pairs, find where the bisectors cross, and rub out the pieces of each bisector that lie inside a cell where a different site is actually closest.

The algebra you need is just coordinate geometry. The edge between two sites $A(x_A, y_A)$ and $B(x_B, y_B)$ is the perpendicular bisector of $[AB]$, so you need its midpoint and the perpendicular gradient.

Midpoint of $[AB]$: $M = \left( \dfrac{x_A + x_B}{2}, \dfrac{y_A + y_B}{2} \right)$ \n Gradient of $[AB]$: $m_{AB} = \dfrac{y_B - y_A}{x_B - x_A}$ \n Perpendicular gradient: $m_\perp = -\dfrac{1}{m_{AB}}$ \n Equation of the edge: $y - y_M = m_\perp (x - x_M)$

In Paper 1 the marks are analytic: each is tied to a specific line of working, either a method mark (M) or an accuracy mark (A), and an accuracy mark depends on the method mark it follows. Follow-through (FT) means an earlier slip need not cost you the marks that depend on it, provided the later step is done correctly on your own figures. But that protection only exists if the method is on the page. Study how each mark below is earned by a specific line.

A vertex is where two edges cross, so you find it by solving the two edge equations simultaneously. Because a vertex is equidistant from three sites, it answers the classic optimisation question: where should a new facility go so that it is as far as possible from every existing site? This is the largest-empty-circle or toxic-waste problem, place a hazardous dump as far as possible from all towns, or a new mast as far as possible from all existing masts to avoid interference. Inside the region, the optimal point is always a Voronoi vertex, and the radius of the largest empty circle is the distance from that vertex to any one of its three equidistant sites.

Sometimes each site carries a value, a weather station records a temperature, a sensor records a pollution level, and you want to estimate the value at a location with no station. Nearest-neighbour interpolation does the simplest possible thing: it gives the location the value of its nearest site, that is, the value of the site whose Voronoi cell contains it. So the Voronoi diagram is exactly the map of which value applies where. The estimate is constant across each cell and jumps at the edges. It is quick and needs no weighting, but it ignores how far the nearest site actually is and takes no account of the second-nearest site, so it can be crude near the borders.

The everyday power of Voronoi diagrams is answering 'which one is nearest?' at a glance. Overlay the diagram for a set of hospitals on a map and every neighbourhood is instantly colour-coded by the hospital that serves it; the same works for schools, fire stations or supermarket depots. Signal coverage is the mirror image: if each mast reaches a fixed radius, the cells tell you which mast a phone should connect to, and comparing a cell's size to that radius reveals gaps where no mast reaches, a coverage hole. Two cautions carry real marks. First, Voronoi 'nearest' is straight-line distance, which can differ from travel distance by road. Second, the diagram assumes the sites are the only thing that matters; a real decision might also weigh capacity or opening hours.

Voronoi diagrams tie the coordinate geometry of 3.1 to 3.3, midpoints, gradients, perpendicular lines and the distance formula, into a single tool for reasoning about proximity. The habit they build, define a feature by distance and then compute it, is exactly the discipline every applied geometry question rewards: state what is equidistant, form the perpendicular bisector, solve for the vertex, measure the radius. Master that chain and the optimisation flavour of the toxic-waste problem generalises far beyond masts and hospitals, to any situation where the best location is the one that balances the distances to a set of fixed points.