Key Idea: A Voronoi diagram divides a plane into regions, one per 'site' (point), where every location in a region is closer to that site than to any other. The boundaries between regions are perpendicular bisectors of the line segments joining adjacent sites. Voronoi diagrams appear in resource allocation, urban planning, and nearest-facility problems.
✅ Key terms and construction
- Site
- Each of the given points (e.g., hospitals, shops). Every site generates one Voronoi cell.
- Cell (region)
- All points in the plane that are closer to one particular site than to any other site.
- Voronoi edge
- A segment of the perpendicular bisector of the line joining two adjacent sites. It marks the boundary between two cells.
- Voronoi vertex
- The point where three Voronoi edges meet. This point is equidistant from exactly three sites — it lies on the circumcircle of those three sites.
- Perpendicular bisector method
- Step 1: Find the midpoint M of the two sites. Step 2: Find the gradient of the line joining the sites. Step 3: The perpendicular gradient is −1/m. Step 4: Write the equation of the bisector through M.
Example: Construct the Voronoi boundary between A(2, 6) and B(8, 2): Midpoint M = ((2+8)/2, (6+2)/2) = (5, 4) Gradient AB = (2−6)/(8−2) = −4/6 = −2/3 Perpendicular gradient = 3/2 Equation through (5, 4) with gradient 3/2: y − 4 = (3/2)(x − 5) → y = (3/2)x − 3.5 Adding a new site: When a new site P is added, find the perpendicular bisectors between P and each of its neighbouring sites. These bisectors create new edges and modify existing cells.
The Voronoi vertex (meeting point of 3 edges) is equidistant from three sites — verify this by calculating distances from the vertex to each of the three sites. In context questions: 'Which site is nearest?' → find which cell the point falls in. 'Where is equidistant from three sites?' → find the Voronoi vertex.
Paper 2 (GDC allowed): Voronoi construction is usually done by hand on a grid — the GDC helps with gradient and equation calculations, but you sketch the diagram. Adding a new site: show the perpendicular bisector equations between the new site and its neighbours. Mark the new vertex clearly and identify which old edges are removed.
IB-style question [7 marks]
Three weather stations are located at A(1, 2), B(9, 2) and C(5, 10) on a grid (units in km). A Voronoi diagram is constructed with the three stations as sites. (a) Find the equation of the perpendicular bisector of [AB]. (b) Find the equation of the perpendicular bisector of [AC], giving your answer in the form ax + by + d = 0 with integer coefficients. (c) Hence find the coordinates of the Voronoi vertex, and verify that it is equidistant from all three stations.
Step by step:
(a) A and B have the same y-coordinate, so [AB] is horizontal and its perpendicular bisector is the vertical line through the midpoint (5, 2).
(b) Midpoint of [AC] is (3, 6); gradient of [AC] is 8/4 = 2, so the perpendicular gradient is −1/2.
Multiply through by 2 and rearrange to integer coefficients.
(c) The Voronoi vertex is where the two bisectors meet. Put x = 5 into x + 2y − 15 = 0.
Verify equidistance by computing the distance from V(5, 5) to each station — all three must be equal.
(a) x = 5. (b) x + 2y − 15 = 0. (c) V(5, 5); VA = VB = VC = 5 km, so V is equidistant from all three stations.