SL 3.6—Voronoi diagrams
- Syllabus
- First assessment 2021
- Objective
- —
- Level
- SL
Voronoi cells assign space to the nearest site
A Voronoi diagram partitions a region so that every point in a cell is closer to its generating site than to any other site. Boundaries lie on perpendicular bisectors between competing sites.
Construct the relevant bisectors, keep only the boundaries that separate nearest-site regions, then use the cell to answer location questions. A new site can remove parts of neighbouring cells rather than simply adding an isolated shape.
If three clinics are sites, a point in Clinic A's cell is predicted to be served by A under a nearest-distance rule. A barrier or travel-time difference would invalidate that simple model.
A Voronoi boundary means equal distance under the chosen metric, not equal demand or guaranteed service quality. State the metric and context assumption.
Terminology: each generator is a site; a cell contains points closest to one site; an edge is an equal-distance boundary between two sites; a vertex is where three or more edges meet. Nearest-neighbour interpolation assigns an unknown point the value of its cell's site. When adding a site, use the supplied perpendicular bisectors to trim neighbouring cells. In the standard toxic-waste-dump task, the solution lies at an intersection of three edges; region areas may require coordinate geometry.