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
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.