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.
Understanding Geometry: Voronoi Diagrams
A useful way to build the diagram is to start with one site at a time. Imagine expanding circles outward from every site at the same speed. A location is claimed by the circle that reaches it first.
Places where two expanding circles arrive together form a border. This picture explains why the borders are straight when ordinary ruler distance is used. It also explains why a site near the outside of the group has a cell that continues forever.
There is no competing site beyond it to stop its region. On a finite map or screen, these endless cells must be clipped to the map boundary.
The shape of a cell depends strongly on the spacing of nearby sites. A site surrounded by close neighbors gets a small cell. An isolated site gets a large one.
This makes Voronoi diagrams useful for judging coverage. For example, a city planner can place clinics as sites and inspect which clinic is nearest from each part of a district.
A large cell may show that people in that area are far from the nearest clinic. In a phone network, tower locations can be treated similarly, although real signal coverage is affected by hills, buildings, power, and interference, not distance alone.
There are a few special cases that matter in geometry. If several sites lie on the same circle, more than three cells can meet at one point. The diagram then has a vertex with several possible connections in its related triangle network.
If two sites are in exactly the same position, the nearest site is not uniquely defined, so one duplicate is normally removed before constructing the diagram. Sites placed in a straight line produce cells with long parallel boundaries.
These cases are not mistakes. They show that a diagram can have ties and symmetries that a simple sketch may hide.
Ordinary distance measures straight line travel, but real problems may need a different rule. On a city street grid, distance can mean the total horizontal and vertical travel. The resulting cells have angled square shaped boundaries rather than the familiar straight edged polygons.
If movement is faster in one direction, distance can be weighted, causing boundaries to shift toward slower routes. This is important in delivery planning and robot navigation. When studying diagrams, draw a few sites first, mark points that seem equally close, then check your claim by comparing distances.
Pay attention to the difference between a boundary, where there is a tie, and the inside of a cell, where one site is clearly nearest. That distinction prevents many common errors.
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.