Math AI HL: Voronoi Diagrams and Applications

Voronoi diagrams are a powerful geometric tool for partitioning space based on proximity to a set of points. For IB Math Applications & Interpretation HL, mastering them is essential for tackling complex, real-world problems in logistics, urban planning, and environmental science.

Core Concept 1: Defining and Constructing Voronoi Diagrams

A Voronoi diagram is a partition of a plane into regions. Each region corresponds to one of a given set of points, called sites or generators. The defining rule is simple: every location within a given Voronoi region is closer to its corresponding site than to any other site in the set. This creates a network of convex polygons, bounded by lines or line segments.

The fundamental tool for constructing these diagrams by hand is the perpendicular bisector. The boundary between the regions of any two sites is a segment of the perpendicular bisector of the line segment connecting those two sites. This makes logical sense: the perpendicular bisector is the set of all points equidistant from the two sites, so it naturally becomes the "decision boundary" for which site is closer.

Construction Method:

1. Plot all given sites on a coordinate plane.
2. For a pair of sites, construct the perpendicular bisector of the segment joining them.
3. The bisector will form a potential edge. You only need to draw the portion of this line that is, in fact, closer to these two sites than to any other. This is determined by checking against other bisectors.
4. Repeat this process for other pairs of nearby sites. The diagram is complete when every site is enclosed in a polygonal region, and all boundaries are in place.

For example, consider three post offices in a town. The Voronoi diagram would show the exact area for which each post office is the closest, allowing the postal service to define delivery zones efficiently.

Core Concept 2: Properties, Vertices, and the Nearest Neighbor Search

Understanding the properties of Voronoi diagrams is key to analyzing them. Each Voronoi region is a convex polygon. The point where three or more region boundaries meet is called a Voronoi vertex. This vertex is the circumcentre of a triangle formed by the three sites whose regions meet at that point, meaning it is equidistant from all three. This property is crucial for both analysis and the link to Delaunay triangulation.

The most immediate application is the nearest-neighbour search. Given any arbitrary point $P$ on the diagram, determining the closest site is instantaneous: you simply identify which Voronoi region $P$ lies in. This is why these diagrams are foundational for "nearest facility" problems, such as finding the closest hospital, fire station, or retail store to a given address. The diagram pre-computes all possible answers to the question "Which site is closest?"

Core Concept 3: Advanced Applications – Optimization and Resource Distribution

The true power of Voronoi diagrams in Math AI HL lies in modeling and optimization. A classic problem is finding the optimal location for a new facility, such as a hospital, to minimize the maximum distance any person in a region must travel. This involves analyzing the existing Voronoi diagram and its vertices.

An even more nuanced application is the toxic waste dump placement or any "least desirable" facility problem. Here, the goal is often to place the facility as far as possible from all population centers or sensitive sites. The solution frequently involves the vertices of the diagram. Since a Voronoi vertex is equidistant from several sites, a candidate location on or near a vertex can represent a local maximum of the minimum distance to any site. You would evaluate these candidate points to find the one that maximizes this minimum distance.

Furthermore, Voronoi diagrams model resource distribution or market areas. If each site represents a store, the Voronoi region is its theoretical catchment area, assuming customers go to the nearest store. Adding a new store requires adding a site to an existing diagram, which involves modifying the regions of nearby sites and drawing new boundaries through the insertion process.

Core Concept 4: The Dual Relationship – Voronoi Diagrams and Delaunay Triangulations

Every Voronoi diagram has a powerful geometric dual called a Delaunay triangulation. To construct the Delaunay triangulation from a Voronoi diagram, you connect any two sites whose Voronoi regions share a common edge. The resulting network of triangles has a paramount property: for any triangle, the circumcircle drawn through its three vertices contains no other sites inside it. This is known as the empty circumcircle property.

This duality is not just theoretical; it has practical computational advantages. Algorithms often compute the Delaunay triangulation first because it is easier to handle, and then derive the Voronoi diagram as its dual by constructing perpendicular bisectors and circumcenters. The Delaunay triangulation itself is used in computer graphics, terrain modeling, and mesh generation because it maximizes the minimum angle of all the triangles, avoiding "skinny" triangles that cause numerical instability.

In analysis, this relationship means that the vertices of your Voronoi diagram correspond to the circumcenters of the triangles in the Delaunay triangulation. Recognizing this link allows you to move fluidly between a partition of space (Voronoi) and a network of connections between points (Delaunay).

Common Pitfalls

1. Incorrect Perpendicular Bisectors: A frequent error is miscalculating the midpoint or the gradient of the perpendicular bisector. Always double-check: find the midpoint $M$, calculate the gradient of the original segment, then take the negative reciprocal for the perpendicular gradient. The equation of the bisector line must pass through $M$.

1. Drawing Full Lines, Not Segments: Students often draw the entire perpendicular bisector line across the entire graph. Remember, you only draw the segment of the bisector that forms the actual boundary between the two regions. This segment ends at a Voronoi vertex or at the point where another site becomes closer. Failing to truncate the lines leads to an incorrect diagram.

1. Misidentifying the Closest Site for a Point: When asked for the closest site to a point $P$ not on a boundary, simply identify the region containing $P$. Do not measure distances to all sites—the diagram has already done that work for you. If $P$ lies on a boundary, it is equidistant from the two sites whose regions meet there.

1. Confusing Voronoi Vertices and Sites: The vertices of the polygonal regions are not the original sites. The sites are inside the regions. Vertices are circumcenters of triangles formed by sites. Mixing these up will lead to significant errors in problems involving maximum or minimum distances.

Summary

• A Voronoi diagram partitions a plane into regions based on the nearest site, using perpendicular bisectors to construct the boundaries between regions.
• Its primary function is enabling an efficient nearest-neighbour search, which is the basis for solving nearest-facility and resource distribution problems.
• Advanced applications include optimizing locations for new facilities and finding suitable locations for undesirable facilities, like a toxic waste dump, by analyzing vertices and regions.
• Every Voronoi diagram has a dual graph called a Delaunay triangulation, formed by connecting sites whose regions share an edge. This triangulation possesses the empty circumcircle property.
• Avoid common construction errors by accurately calculating bisectors, drawing only the relevant boundary segments, and clearly distinguishing between sites and Voronoi vertices in your analysis.