A Voronoi diagram divides a plane into regions based on distance to a set of special points called sites or seeds. Each region contains all points closer to one site than to any other site. This idea matters because it turns a scattered set of points into a useful map of nearest neighbors.
Voronoi diagrams appear in geometry, computer graphics, geography, biology, robotics, and data science.
The boundaries of a Voronoi cell are made from points that are exactly the same distance from two neighboring sites. In the plane, these boundaries are line segments or rays that lie on perpendicular bisectors between pairs of sites. When three or more cells meet at a vertex, that point is equally distant from three or more sites.
Connecting neighboring sites across shared Voronoi edges gives the Delaunay triangulation, a closely related structure used for meshes and spatial analysis.
Key Facts
- A Voronoi cell for site A contains all points P such that d(P, A) <= d(P, B) for every other site B.
- The boundary between two sites A and B lies on the perpendicular bisector of segment AB.
- A Voronoi vertex is usually equidistant from three sites, so d(V, A) = d(V, B) = d(V, C).
- Voronoi diagrams partition the plane into nonoverlapping regions that cover the whole plane.
- Two sites are Delaunay neighbors if their Voronoi cells share an edge.
- Distance in the standard plane is often Euclidean: d = sqrt((x2 - x1)^2 + (y2 - y1)^2).
Vocabulary
- Voronoi diagram
- A division of the plane into regions where each region contains the points nearest to one chosen site.
- Site
- A point used as a seed for one Voronoi region.
- Voronoi cell
- The region of all points closer to one site than to any other site.
- Perpendicular bisector
- A line that crosses a segment at its midpoint and forms a right angle with it.
- Delaunay triangulation
- A network of triangles formed by connecting sites whose Voronoi cells share an edge.
Common Mistakes to Avoid
- Drawing cell boundaries halfway by eye, which is wrong because boundaries must be perpendicular bisectors between sites, not just visually centered lines.
- Assuming every cell is the same size, which is wrong because cell shape and area depend on how close each site is to its neighbors.
- Forgetting that outer cells can extend forever, which is wrong because a finite set of sites in an infinite plane often has unbounded Voronoi regions around the outside.
- Connecting all sites to make the Delaunay triangulation, which is wrong because only sites with shared Voronoi edges should be connected.
Practice Questions
- 1 Two sites are A(0, 0) and B(6, 0). Find the equation of the Voronoi boundary between them.
- 2 For sites A(0, 0), B(4, 0), and C(0, 4), find the point that is equidistant from all three sites.
- 3 A city wants to assign each home to its nearest fire station. Explain how a Voronoi diagram could help, and describe one limitation of using straight-line distance for this task.