IB Math AI: Voronoi Diagrams

Voronoi diagrams are a powerful tool for spatial analysis, transforming a simple set of points into a map of influence and proximity. In IB Math Applications and Interpretation, you study them not as abstract geometry but as a practical framework for solving real-world problems. From determining the closest hospital to optimizing cell tower coverage, understanding how to construct and interpret these diagrams allows you to model and analyze the spatial relationships that shape our world.

What is a Voronoi Diagram?

A Voronoi diagram is a partition of a plane into regions based on the distance to a specific set of points. Each of these points is called a site or a generator point. The fundamental rule is simple: every location within a given Voronoi region is closer to that region's site than to any other site in the diagram. The boundaries between regions, called Voronoi edges, are composed of points that are equidistant from the two nearest sites. Where three or more edges meet, you find a Voronoi vertex, a point equidistant to three (or more) sites.

Imagine a city with several fire stations. The ideal response area for each station is the region where it is the closest station—this is a Voronoi region. The boundaries between these areas are the lines where response times from two different stations would be equal. This practical application illustrates the core purpose of a Voronoi diagram: to solve nearest neighbor problems visually and mathematically.

Constructing a Voronoi Diagram

For the IB Math AI course, you are expected to construct a diagram given two or three sites. The construction relies on a fundamental geometric concept: the perpendicular bisector.

Step 1: Plot the Sites Begin by accurately plotting your given sites on a coordinate plane. Label them clearly (e.g., A, B, C).

Step 2: Draw Perpendicular Bisectors For each pair of sites, construct the perpendicular bisector of the line segment connecting them. The perpendicular bisector is the set of all points equidistant from the two endpoints. This is crucial because the Voronoi edge between two sites is a segment of this perpendicular bisector.

• With two sites (A and B): The diagram is simply the perpendicular bisector of line segment AB. All points on one side are closer to A, and all points on the other side are closer to B.

Step 3: Identify Regions and Vertices (for three sites) With three sites (A, B, C), you will draw three perpendicular bisectors (between A-B, A-C, and B-C). In a typical non-collinear arrangement, these three lines will intersect at a single point. This intersection point is the Voronoi vertex. The vertex is equidistant from all three sites (A, B, and C). The regions are formed by the segments of the bisectors that are closest to each site.

A worked example clarifies this. Let sites be A(2, 5), B(6, 3), and C(4, 7).

1. Find the midpoint of AB: $((2+6)/2,(5+3)/2)=(4,4)$.
2. The gradient of AB is $(3-5)/(6-2)=-2/4=-1/2$. Therefore, the gradient of its perpendicular bisector is $2$.
3. The equation of the bisector for AB is $y-4=2(x-4)$ or $y=2x-4$.
4. Repeat for another pair, like AC. Midpoint of AC is $(3,6)$. Gradient of AC is $(7-5)/(4-2)=1$. Perpendicular gradient is $-1$.
5. Equation for AC bisector: $y-6=-1(x-3)$ or $y=-x+9$.
6. Find the intersection of $y=2x-4$ and $y=-x+9$. Set $2x-4=-x+9$, giving $3x=13$, so $x=13/3\approx 4.33$. Then $y=-(13/3)+9=14/3\approx 4.67$.
7. This intersection point $(13/3,14/3)$ is the Voronoi vertex. Draw the relevant segments of each bisector radiating from this vertex to form the three regions.

Finding the Coordinates of a Voronoi Vertex

As shown in the construction, the vertex is found by solving the equations of two perpendicular bisectors simultaneously. You must ensure you are using the correct bisectors. The vertex is defined by three sites; therefore, it lies on the bisectors for each pair of those three sites. Solving any two of these three bisector equations will yield the vertex coordinates. Remember, the vertex's key property is that its distance to each of the three defining sites is equal. You can verify your coordinates by checking that $d_{\text{vertex to A}}=d_{\text{vertex to B}}=d_{\text{vertex to C}}$ using the distance formula: $d=\sqrt{(x_2-x_1{)}^2+(y_2-y_1{)}^2}$.

Real-World Applications and Problem Solving

The true power of Voronoi diagrams lies in their application. The IB exam will present problems where you must interpret or use a given diagram.

1. Nearest Facility Location: This is the most direct application. Given a point P on the diagram, you determine which region it lies in to identify the nearest site (e.g., the closest hospital, store, or emergency service).

2. Resource Allocation and Urban Planning: Planners can use Voronoi diagrams to ensure equitable access to resources like parks, schools, or libraries. By analyzing the size and shape of the regions, they can identify underserved areas. If a new site is added (e.g., a new school), you would need to redraw the diagram to see how the regions change, a process called region addition.

3. Maximizing Distance from Undesirable Sites: A more advanced question might ask: "Where should a house be built to be as far as possible from multiple industrial plants?" The point that maximizes the minimum distance to any plant is often found at a Voronoi vertex.

4. Largest Empty Circle Problem: Among a set of sites, what is the largest circle you can draw that contains no sites inside it? The center of this circle will be at a Voronoi vertex, and its radius will be the distance from that vertex to the nearest site(s). This has applications in facility placement (e.g., placing a new warehouse that is not too close to competitors).

Relationship to Delaunay Triangulation

Every Voronoi diagram has a dual graph called a Delaunay triangulation. This is a network of triangles formed by connecting the sites whose Voronoi regions share an edge. The key property is that the circumcircle of any triangle in a Delaunay triangulation will contain no other sites inside it. This relationship is important in higher computational geometry, but for IB Math AI, you should understand the basic concept of duality: vertices in the Voronoi diagram correspond to triangles in the Delaunay, and edges correspond (are perpendicular) to the connections between sites. This triangulation is often used in computer graphics and terrain modeling because it creates "well-shaped" triangles.

Common Pitfalls

Misplacing the Perpendicular Bisector: The most frequent error is calculating the gradient or midpoint incorrectly. Always double-check your arithmetic. The perpendicular gradient is the negative reciprocal. If the segment gradient is $m$, the bisector gradient is $-1/m$.

Confusing Regions and Vertices: Remember, a region belongs to a single site. A vertex is a point shared by three (or more) regions. Do not label a vertex as belonging to a specific site.

Assuming All Bisectors are Edges: When constructing a diagram with more than three sites, not every perpendicular bisector you draw will become a Voronoi edge. Only the segments that are actually closest to the sites form the final edges. Others will be excluded because a third site is closer. Always test by checking distances.

Misinterpreting "Largest Empty Circle": The center is at a Voronoi vertex, not at a random point in a region. The radius is the distance from that vertex to any of its three defining sites—they are all equal.

Summary

• A Voronoi diagram partitions space into regions where any point within a region is closest to that region's site. The boundaries are formed from segments of perpendicular bisectors.
• Construction involves plotting sites, drawing perpendicular bisectors between pairs, and finding their intersections (Voronoi vertices) to define the region boundaries.
• Its primary application is solving nearest neighbor problems in contexts like facility location, urban planning, and resource allocation.
• Advanced problem-solving includes finding the largest empty circle, whose center is located at a Voronoi vertex.
• The diagram is mathematically dual to the Delaunay triangulation, where sites connected in the triangulation correspond to regions that share an edge in the Voronoi diagram.