IB Mathematics Applications & Interpretation SL 3.6—voronoi Diagrams Notes

Why Voronoi Diagrams Exist: Carving A Map By Who Is Nearest

1. Scatter some points on a map, mobile-phone masts, coffee shops, rainfall gauges, or hospitals, and a natural question follows: for any spot, which one is nearest?
2. A Voronoi diagram answers this for every location at once by splitting the whole map into regions, one region per point, so that everywhere in a region shares the same nearest point.
3. This is a genuinely applied tool: town planners, ecologists and network engineers all use it to model catchment areas and coverage.
4. It is built entirely from the perpendicular bisectors of SL 3.5, so if you can find the equal-distance line between two points, you can read a Voronoi diagram.

The Parts Of A Voronoi Diagram

1. Four pieces of vocabulary describe every Voronoi diagram, and exam questions expect you to use them precisely.
2. Sites are the original points, such as the masts or shops; every site owns exactly one region.
3. Cells are the region around a site containing all points closer to that site than to any other.
4. Edges are the straight boundaries between neighbouring cells; each edge is part of the perpendicular bisector of the two sites it separates.
5. Vertices are the points where three or more edges meet; a vertex is equidistant from three sites at once.

Building The Diagram From Perpendicular Bisectors

1. Between any two neighbouring sites, the boundary is the set of points equally close to both, which is exactly their perpendicular bisector.
2. So to build a diagram by hand you draw the perpendicular bisector of each pair of nearby sites, then keep only the portions that actually border two cells.
   1. A vertex forms where the bisectors of three sites all pass through one point, so that point is the same distance from all three.
3. Because every edge is a straight perpendicular bisector, Voronoi cells are always made of straight sides and are convex (no dents).

Adding A New Site

1. If a new site is added, for example a new shop opens, only the nearby part of the diagram changes.
2. Draw the perpendicular bisectors between the new site and each of its neighbouring sites.
   1. The new cell is carved out of the old cells, so the new site takes territory from the sites around it, and those old edges get trimmed back.
3. Sites far away are unaffected, so you never need to redraw the whole diagram.

Nearest-Neighbour Interpolation: Estimating A Value

1. Sometimes each site carries a measured value, such as the rainfall recorded at that gauge, and you want to estimate the value at a new location.
2. Nearest-neighbour interpolation gives that new location the value of the site whose cell it falls inside.
   1. The reasoning is simple: the nearest gauge is the best single guess, so the whole cell is assigned its site's value.
3. Its limitation is that it treats the value as constant across a whole cell and jumps suddenly at an edge, which is rarely true of real quantities like rainfall.

The Toxic Waste Dump Problem: The Largest Empty Circle

1. A classic AI question asks where to place something you want as far as possible from every site, such as a toxic-waste dump far from all towns.
2. This is the largest empty circle problem: find the point whose distance to its nearest site is as large as possible.
   1. The key result: the best point is always a vertex of the Voronoi diagram (within the region of interest).
   2. A vertex is a local 'furthest from the nearby sites' point because it is equidistant from three sites, so no small move increases the distance to all of them.
3. The method: at each vertex, measure the distance to its nearest site (using the distance formula), then choose the vertex with the largest such distance.