Voronoi Diagrams
Use perpendicular bisectors to divide a plane into nearest-neighbour regions.
Terminology
- Sites: the given points.
- Cells: regions containing points closest to one site.
- Edges: boundaries between cells, formed from perpendicular bisectors.
- Vertices: points where three or more edges meet.
Nearest-neighbour interpolation
If a value is known at each site, estimate the value at a new point using the value of the closest site. In other words, points in the same Voronoi cell inherit the site’s value.
Toxic waste dump idea
To place a facility as far as possible from the nearest town, check the Voronoi vertices. The best position usually occurs at a vertex because vertices are equally distant from three or more nearby sites.