Voronoi diagrams in HL AI: the topic students forget exists

Every year, it happens. A student comes to me after an HL AI mock exam, looking defeated. They’ve aced calculus, probability, even linear algebra. But then they hit a question about Voronoi diagrams and draw a blank. "Mr. Bromfield," they'll say, "I completely forgot we even covered this." It’s not an isolated incident. Voronoi diagrams, despite their practical applications and visual nature, often fade into the background for my HL AI students. They are one of those topics that can surprise students in an exam.

My goal here is to pull Voronoi diagrams back into the spotlight. If you are an IB HL AI student, or a parent supporting one, this article will refresh your understanding of what Voronoi diagrams are, where they fit into the HL AI syllabus, and how to approach them effectively for your exams. This is a topic that requires careful drawing and interpretation, and often catches students off guard.

What Exactly is a Voronoi Diagram?

At its core, a Voronoi diagram is a partition of a plane into regions. Each region contains exactly one 'seed' point, and every point within that region is closer to its seed point than to any other seed point. Imagine a set of competing WiFi routers in a city. A Voronoi diagram would show you which router you're connected to based on your location – you'll connect to the closest one. The boundaries of these regions are equidistant lines between two adjacent seed points. These boundaries are perpendicular bisectors.

In the IB HL AI syllabus, we formalize this. Given a set of discrete points $P = \{p_1, p_2, \ldots, p_n\}$ in a plane, the Voronoi cell $V(p_i)$ associated with a point $p_i$ is defined as:

where $d(x, y)$ is the Euclidean distance between points $x$ and $y$. My students find understanding this definition crucial, as it underpins all calculations and constructions.

Construction and Key Features

Constructing a Voronoi diagram by hand is a skill my students need for Paper 2. It involves drawing perpendicular bisectors. For any two seed points $A$ and $B$, the set of points equidistant from $A$ and $B$ is the perpendicular bisector of the segment $AB$. Each edge in a Voronoi diagram is a segment of such a perpendicular bisector. Each vertex in a Voronoi diagram is equidistant from at least three seed points. This is a key property and often a source of exam questions.

Let's take a simple example. Suppose we have three seed points: $A(1,1)$, $B(5,1)$, and $C(3,5)$.

1. First, find the perpendicular bisector of $AB$. The midpoint of $AB$ is $\left(\frac{1+5}{2}, \frac{1+1}{2}\right) = (3,1)$. The slope of $AB$ is $\frac{1-1}{5-1} = 0$. So, the perpendicular bisector is a vertical line $x=3$.
2. Next, find the perpendicular bisector of $BC$. The midpoint of $BC$ is $\left(\frac{5+3}{2}, \frac{1+5}{2}\right) = (4,3)$. The slope of $BC$ is $\frac{5-1}{3-5} = \frac{4}{-2} = -2$. The perpendicular slope is $\frac{1}{2}$. The equation of the bisector is $y-3 = \frac{1}{2}(x-4)$, which simplifies to $y = \frac{1}{2}x+1$.
3. Finally, find the perpendicular bisector of $AC$. The midpoint of $AC$ is $\left(\frac{1+3}{2}, \frac{1+5}{2}\right) = (2,3)$. The slope of $AC$ is $\frac{5-1}{3-1} = \frac{4}{2} = 2$. The perpendicular slope is $-\frac{1}{2}$. The equation of the bisector is $y-3 = -\frac{1}{2}(x-2)$, which simplifies to $y = -\frac{1}{2}x+4$.

The intersection of these bisectors forms the vertices of the Voronoi cells. The intersection of $x=3$ and $y = \frac{1}{2}x+1$ gives $y = \frac{1}{2}(3)+1 = 2.5$, so $(3, 2.5)$. This is the Voronoi vertex equidistant from $A$, $B$, and $C$. All points on the boundary between $A$ and $B$ are closer to $A$ than $B$ on one side, and closer to $B$ than $A$ on the other. This visual construction is where many students make mistakes if they rush.

Applications in IB HL AI Context

Why do we study Voronoi diagrams in HL AI? Their applications are widespread, particularly in areas relevant to artificial intelligence and data science. In my classroom, we discuss examples like:

• Location optimization: Placing emergency services (fire stations, hospitals) to minimize response times. Each station becomes a seed point, and the Voronoi cells show its service area. This is a common exam scenario.
• Ecology: Analyzing territorial boundaries of animal species based on their nests or dens.
• Computer graphics: Generating natural-looking textures and patterns.
• Geo-spatial analysis: Identifying areas of influence for stores or cell towers.
• Machine learning (K-Nearest Neighbors): While not a Voronoi diagram directly, the underlying concept of proximity and nearest neighbors is very similar. The Voronoi diagram provides a clear visual representation of decision boundaries in a 1-Nearest Neighbor classifier.

Exam questions often present a scenario and ask students to apply Voronoi diagrams to solve a problem, such as determining the optimal location for a new facility or identifying which service point covers a given coordinate. My students must not only construct the diagram but also interpret it in the context of the problem.

Navigating Exam Questions: What to Expect

Voronoi diagram questions usually appear in Paper 2 or Paper 3 for HL AI. They often combine geometric construction with interpretation and problem-solving. Here’s what my students usually encounter:

• Drawing the diagram: Given a set of seed points, construct the Voronoi diagram. This is where precision in drawing perpendicular bisectors is key.
• Finding vertices and equations: Calculate the coordinates of a specific vertex or the equation of a specific boundary line. This requires using simultaneous equations to find the intersection of perpendicular bisectors.
• Identifying regions: Determine which seed point is closest to a given test point.
• Adding new points: How does the diagram change if a new seed point is introduced? This tests understanding of how new bisectors are formed.
• Real-world context: Apply the diagram to a scenario (e.g., cell towers, hospitals) to answer a question about optimal placement or coverage.
• Area/Perimeter calculations: Less common, but sometimes students are asked to calculate the area or perimeter of a Voronoi cell, especially if the diagram is bounded.

It's vital for my students to practice these types of questions. They can review past paper questions, specifically looking at Paper 2 and Paper 3 for HL AI. Resources like our study notes and flashcards often include key concepts and worked examples that cover this topic.

When solving these questions, remember the direct link to coordinate geometry. Equations of lines, midpoints, gradients, and distances are all essential. If your coordinate geometry skills are not solid, Voronoi diagram questions will be challenging. I encourage students to review basic coordinate geometry if they find themselves struggling here. We also cover relevant coordinate geometry concepts in our SL AA Paper 1 resources, which apply to HL AI too.

Final Thoughts and Next Steps

Don't let Voronoi diagrams be the topic you forget exists. They are a distinct part of the IB HL AI syllabus, particularly relevant for Paper 2 and Paper 3. They test your ability to combine geometric construction with algebraic calculation and real-world interpretation. My students who excel at this topic are those who practice their drawing skills and understand the underlying geometric principles of perpendicular bisectors and equidistance.

My advice is to dedicate specific revision time to Voronoi diagrams. Work through past paper questions. If you find yourself rusty on coordinate geometry, revisit those fundamentals. A strong grasp of this topic can make a difference in your final exam score, ensuring you don't leave easy marks on the table. Make sure to check out our Paper 3 HL AI guide for more specific strategies related to this topic.