How Voronoi Diagrams Partition a Plane in Mathematics
This article explains the mathematical principles and computational methods behind Voronoi diagrams. It covers how these diagrams divide a continuous plane into distinct regions based on the distance to a specific set of pre-defined points. By exploring the core geometric components, the role of perpendicular bisectors, varying distance metrics, and the primary algorithms used to compute them, you will understand the exact mechanics of Voronoi partitioning in computational mathematics.
The Core Components
To understand how a Voronoi diagram partitions a plane, you must first understand its three basic elements:
- Sites (or Seeds): A finite set of distinct points placed on a plane.
- Voronoi Cells (or Regions): The partitioned areas of the plane. Each site has one corresponding cell. A cell consists of all the points on the plane that are closer to that specific site than to any other site.
- Voronoi Edges and Vertices: The boundaries that separate the cells. An edge is a line segment of points that are equidistant to two nearest sites. A vertex is a point where three or more edges meet, meaning it is equidistant to three or more sites.
The Geometric Mechanism: Half-Planes and Bisectors
Mathematically, a Voronoi diagram partitions a plane by calculating the intersection of half-planes.
Imagine just two sites on a plane, Point A and Point B. To divide the plane into regions of closeness between them, you draw a straight line connecting A and B, and then draw a perpendicular bisector right through the middle of that line. This bisector divides the plane into two "half-planes." Every point on one side of the bisector is closer to Point A, and every point on the other side is closer to Point B.
When a plane has multiple sites, the Voronoi cell for a single site (Point A) is formed by drawing perpendicular bisectors between Point A and every other site on the plane. The smallest enclosed area around Point A—formed by the intersecting half-planes—becomes its Voronoi cell. Because the cell is formed by the intersection of half-planes, every Voronoi cell is a convex polygon (some of which may be unbounded and extend to infinity at the edges of the plane).
Distance Metrics
The shape of the partitioned regions depends entirely on how "distance" is mathematically defined. In computational mathematics, two metrics are primarily used:
- Euclidean Distance: This is the standard straight-line distance between two points, calculated using the Pythagorean theorem. Given two points \((x_1, y_1)\) and \((x_2, y_2)\), the distance is \(\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}\). Euclidean Voronoi diagrams always produce straight-line edges and convex polygon cells.
- Manhattan Distance (Taxicab Geometry): This measures distance based on a grid, where movement is only allowed horizontally and vertically. The distance is calculated as \(|x_1 - x_2| + |y_1 - y_2|\). Using this metric results in Voronoi edges that consist of horizontal, vertical, and 45-degree diagonal line segments, creating jagged, non-standard polygon regions.
Computational Algorithms
Calculating perpendicular bisectors for every pair of points is computationally inefficient for large datasets, requiring \(O(n^2)\) time. Computational mathematics relies on optimized algorithms to generate Voronoi partitions in \(O(n \log n)\) time.
Fortune’s Algorithm This is a sweep-line algorithm. Imagine a horizontal line sweeping from the top of the plane to the bottom. As the sweep-line hits a site, a parabola is formed behind the line. This parabola represents all points equidistant from the site and the sweep-line itself. The algorithm maintains a "beach line" made of these intersecting parabolas. The points where the parabolas intersect trace out the Voronoi edges as the sweep-line moves down the plane.
Delaunay Triangulation (The Dual Graph) A Voronoi diagram can also be constructed by first computing its mathematical dual: the Delaunay triangulation. This method connects all the sites into triangles such that no site lies inside the circumcircle (a circle that passes through all three vertices) of any triangle. Once the triangulation is complete, the centers of these circumcircles become the Voronoi vertices. Connecting the centers of adjacent triangles directly generates the Voronoi edges, successfully partitioning the plane.