Home / IB DP Maths / Application and Interpretation HL / IB Mathematics AI SL Voronoi diagrams MAI Study Notes

IB Mathematics AI SL Voronoi diagrams MAI Study Notes - New Syllabus

IB Mathematics AI SL Voronoi diagrams MAI Study Notes

LEARNING OBJECTIVE

  • Voronoi diagrams:

Key Concepts: 

  • Voronoi Diagrams
  • Toxic Waste Dump Problem

MAI HL and SL Notes – All topics

VORONOI DIAGRAMS 

A Voronoi diagram-also known as a Voronoi tessellation or Voronoi partition-is a geometric structure that divides a space into distinct regions based on proximity to a specific set of points called seeds or sites. Each region consists of all the points in the space that are closer to one particular seed than to any other. Voronoi diagrams are widely used in various fields such as computer graphics, geographical information systems (GIS), robotics, urban planning, and biology, due to their ability to model spatial relationships and influence zones effectively.

Consider the following simple scenario.

A region contains two sites A and B.

We wish to separate the region into two smaller regions:

 the region of A: all the points which are closest to the site A
the region of B: all the points which are closest to the site B

It is pretty obvious that the border of the two regions will be the perpendicular bisector of the line segment AB.

This is perhaps the simplest Voronoi diagram! The two regions are called cells. The line between the two cells is called an edge.

Well, there is an even simpler case: The trivial Voronoi diagram with only one site and one cell (which is the whole region).

Suppose we have three sites, A, B and C.
If the three sites are collinear (they lie on the same line) the Voronoi diagram is pretty obvious:

The three edges are parallel.
If, otherwise, the three sites form a triangle, the Voronoi diagram looks like:

Particularly for this case of three sites, we know that the edges between the three cells are the perpendicular bisectors of the sides.
We know from Geometry that the three edges meet at the same point. The point P where the edges meet is called a vertex.
We know that all points in cell A are closer to A than to B or C.

Let us add one more site D (see below). We obtain four cells and the edges meet at the two vertices P and Q.

Usually, the sites are given by Cartesian coordinates.

Suppose that the four sites in the diagram above have coordinates A(2,3), B(8,3), C(6,7), and D(10,5).

 Edge L₁ between A and B: it has equation x = 5 
Edge L₂ between A and C: we find the perpendicular bisector:
 Slope of AC: \( m_{AC} = \frac{7-3}{6-2} = 1 \). Hence, the slope of the perpendicular bisector \( m_{\perp} = -1 \).
 Midpoint of AC is M(4,5).
Equation of L₂: \( y – 5 = -1(x – 4) \), that is \( y = -x + 9 \).
 Vertex P: the intersection between L₁ and L₂. This is P(5,4).

In a similar way, we find:

 Edge L₃ between B and C: \( y = \frac{1}{2}x + \frac{3}{2} \).
 Edge L₄ between B and D: \( y = -x + 13 \).
 Edge L₅ between C and D: \( y = 2x – 10 \).
 Vertex Q: \( \left( \frac{23}{3}, \frac{16}{3} \right) \).

Example

For this Voronoi diagram:

a) Give coordinates of a vertex that is equidistant from A,B & F 

b) (3,4) is closest to which site?

c) Give coordinates of any point equidistant from B & C 

d) Which site has the smallest cell?

▶️Answer/Explanation

Solution:

a) The coordinates of a vertex that is equidistant from A,B & F $\longrightarrow$ (3,8)

b) (3,4) is closest to Site D

c) The coordinates of any point equidistant from B & C $\longrightarrow$ (9,6) [or (7,10)]

d)  It may not look obvious at this scale, but every cell is infinite, apart from B, which has edges on all sides.

NEAREST NEIGHBOR INTERPOLATION

Nearest Neighbor Interpolation is a method used to estimate unknown values based on the closest known data points.

Given a set of points \(\{(x_i, y_i, f_i)\}_{i=1}^n\), where \((x_i, y_i)\) are coordinates and \(f_i\) is a known value (e.g., temperature, pixel intensity), the interpolated value \(\hat{f}(x,y)\) at a new point \((x,y)\) is given by:

$\hat{f}(x,y) = f_k \quad \text{where} \quad k = \arg\min_{i} \sqrt{(x – x_i)^2 + (y – y_i)^2}$

Algorithm Steps:

1. Input: A set of known points \(\{(x_i, y_i, f_i)\}\) and a query point \((x,y)\).
2. Compute distances from \((x,y)\) to all \((x_i, y_i)\).
3. Find the nearest neighbor \((x_k, y_k)\) with the smallest distance.
4. Assign \(\hat{f}(x,y) = f_k\).

Example (Image Upscaling)

Consider a \(2 \times 2\) grayscale image:

$
\begin{bmatrix}
100 & 150 \\
200 & 50 \\
\end{bmatrix}
$

We upscale it to \(4 \times 4\) using nearest-neighbor interpolation.

▶️Answer/Explanation

Solution:

Step 1: Map original coordinates \((0,0), (0,1), (1,0), (1,1)\) to new coordinates in \([0,3] \times [0,3]\).
Step 2: For each new pixel \((i,j)\), find the closest original pixel.

$
\begin{bmatrix}
100 & 100 & 150 & 150 \\
100 & 100 & 150 & 150 \\
200 & 200 & 50 & 50 \\
200 & 200 & 50 & 50 \\
\end{bmatrix}
$

Example (Temperature Estimation)

Given weather stations:

\(A = (1,1), f_A = 25°C\)
 \(B = (4,5), f_B = 20°C\)
\(C = (6,2), f_C = 30°C\)

Estimate temperature at \(P = (3,3)\).

▶️Answer/Explanation

Solution:

Compute distances:
$d(P,A) = \sqrt{(3-1)^2 + (3-1)^2} = 2.83$
$d(P,B) = \sqrt{(3-4)^2 + (3-5)^2} = 2.24$
$d(P,C) = \sqrt{(3-6)^2 + (3-2)^2} = 3.16$
 Nearest neighbor: \(B\) (smallest distance).
 Interpolated value: \(\hat{f}(P) = f_B = 20°C\).

Advantages & Disadvantages

Pros:

Simple and computationally fast.
 Preserves sharp edges (useful in pixel art).

Cons:

Produces blocky artifacts in images.
Less accurate than bilinear/cubic interpolation for smooth data.

THE "TOXIC WASTE DUMP" PROBLEM

This is a classic problem in computational geometry where we need to find the optimal location to place a toxic waste dump such that it is as far as possible from a set of given cities (or sites).

Steps:

Construct the Voronoi Diagram for the given cities (sites).
Find the Voronoi vertex (a point where three or more Voronoi edges meet) that is farthest from any city.
This vertex is the optimal location for the toxic waste dump because it maximizes the minimum distance to the nearest city.

Example

Find the coordinates of the centre of the LEC for the Voronoi in the grid shown:

▶️Answer/Explanation

Solution:

Either at vertex: (2,4) or (8,4).

Test distances to adjacent vertices, then choose.

First: (2,4) to A(4,7)

$=\sqrt{(7-4)^2+(4-2)^2}=\sqrt{9+4}=\sqrt{13}$.

Dist. from (8,4) to B(13,4) is clearly 5. $\sqrt{13} < 5$, hence (2,4) is our answer.

Some apparent properties:

Any point within cell F is closest to F.
Any point on the edge between cells C and F is equidistant to sites C and F (and these are the closest sites).
The vertex between cells C, F, and D is equidistant to sites C, F, and D (and these are the closest sites). If we draw a circle with center at this vertex, it touches C, F, and D, and all other sites are outside the circle.
 Any vertex connects at least three edges.

Applications of Voronoi Diagrams

Voronoi diagrams are geometric structures that partition space into regions based on distance to a given set of points (called sites). Each region (Voronoi cell) consists of all points closer to one particular site than to any other. These diagrams have numerous applications in various fields:

  • Computer Graphics & Game Design – Used for procedural terrain generation, texture synthesis, and AI pathfinding.
  • Robotics & Autonomous Navigation – Helps in obstacle avoidance and optimal path planning.
  • Biology & Ecology – Models animal territories, plant competition, and cell structures.
Scroll to Top