IB Mathematics AI – Topic 3

1. Sites (Seeds/Generators):

The given set of points in the plane, usually denoted as A, B, C, D, etc.

Example: Locations of hospitals, schools, or stores

Notation: Sites are typically marked with filled dots •

2. Voronoi Cells (Regions):

The regions surrounding each site

Each cell contains all points in the plane that are closer to that site than to any other site

Definition: For site A, the Voronoi cell is:

\[ V(A) = \{P : d(P, A) \leq d(P, B) \text{ for all sites } B\} \]

3. Voronoi Edges:

The boundaries between adjacent Voronoi cells

Each edge is part of the perpendicular bisector of the line segment joining two sites

All points on an edge are equidistant from exactly two sites

4. Voronoi Vertices:

Points where three or more Voronoi edges meet

Each vertex is equidistant from at least three sites

Centers of empty circles that pass through exactly three sites

⚠️ Common Pitfalls & Tips:

• Voronoi edges extend to infinity unless bounded by a frame
• Each site has exactly one Voronoi cell
• Cells can be unbounded (extending infinitely)
• Adjacent cells share an edge (perpendicular bisector)

Finding Perpendicular Bisector Between Two Sites:

Step 1: Find the midpoint M

For sites A\((x_1, y_1)\) and B\((x_2, y_2)\):

\[ M = \left(\frac{x_1 + x_2}{2}, \frac{y_1 + y_2}{2}\right) \]

Step 2: Find gradient of AB

\[ m_{AB} = \frac{y_2 - y_1}{x_2 - x_1} \]

Step 3: Find perpendicular gradient

\[ m_{\perp} = -\frac{1}{m_{AB}} \]

Step 4: Write equation of perpendicular bisector

Using point-gradient form through M:

\[ y - y_M = m_{\perp}(x - x_M) \]

Or rearrange to general form: \(ax + by + d = 0\)

⚠️ Common Pitfalls & Tips:

• Remember: perpendicular gradient is negative reciprocal
• Every point on the perpendicular bisector is equidistant from both sites
• The perpendicular bisector forms the edge between two Voronoi cells
• Use GDC to verify calculations

Solution:

Step 1: Find midpoint M

\[ M = \left(\frac{2 + 8}{2}, \frac{3 + 7}{2}\right) = (5, 5) \]

Step 2: Find gradient of AB

\[ m_{AB} = \frac{7 - 3}{8 - 2} = \frac{4}{6} = \frac{2}{3} \]

Step 3: Find perpendicular gradient

\[ m_{\perp} = -\frac{1}{2/3} = -\frac{3}{2} \]

Step 4: Write equation using M(5, 5)

\[ y - 5 = -\frac{3}{2}(x - 5) \]

\[ y - 5 = -\frac{3}{2}x + \frac{15}{2} \]

\[ 2y - 10 = -3x + 15 \]

\[ 3x + 2y - 25 = 0 \]

Answer: 3x + 2y - 25 = 0

Method 1: Visual Identification

If you have a Voronoi diagram drawn:

1. Locate the point on the diagram
2. Identify which cell contains the point
3. The site for that cell is the nearest neighbour

Method 2: Distance Calculation

Calculate distance from point P to each site:

\[ d(P, A) = \sqrt{(x_P - x_A)^2 + (y_P - y_A)^2} \]

The site with minimum distance is the nearest neighbour

Applications:

• Service allocation: Which hospital should serve a location?
• Market analysis: Which store is closest to a customer?
• Emergency response: Which station should respond?
• Data estimation: Estimating unknown values based on nearest known data

⚠️ Common Pitfalls & Tips:

• Points on edges are equidistant from two sites
• Points at vertices are equidistant from three or more sites
• Use GDC to calculate distances efficiently
• Can compare squared distances (avoid square root for speed)

Key Concept: Largest Empty Circle

Find the largest circle that:

• Contains no sites in its interior
• Is centered at a point in the plane
• Has maximum radius

Solution Approach:

The center of the largest empty circle is located at a Voronoi vertex

Why Voronoi Vertices?

• Voronoi vertices are equidistant from three or more sites
• These points are locally as far as possible from nearby sites
• One of these vertices maximizes the minimum distance to any site

Steps to Solve:

1. Construct the Voronoi diagram for all sites (towns)
2. Identify all Voronoi vertices
3. For each vertex, calculate the distance to the nearest site(s)
4. The vertex with the maximum distance is the optimal location
5. This maximum distance is the radius of the largest empty circle

Alternative Method (Without Full Diagram):

If given partial Voronoi diagram or specific vertices:

1. Calculate distance from each given vertex to nearest site
2. Compare distances
3. Maximum distance identifies the best location

⚠️ Common Pitfalls & Tips:

• The optimal point is ALWAYS at a Voronoi vertex
• Don't forget to check all vertices in bounded region
• Consider vertices at the boundary if region is bounded
• Use GDC to calculate distances accurately

Solution:

Strategy: The optimal location is the Voronoi vertex. We just need to calculate the distance from this vertex to any of its equidistant sites.

Calculate distance from V(3, 1.25) to any site (e.g., A(0, 0)):

\[ d(V, A) = \sqrt{(3-0)^2 + (1.25-0)^2} = \sqrt{9 + 1.5625} = \sqrt{10.5625} \approx 3.25 \]

Verify with another site (e.g., B(6, 0)):

\[ d(V, B) = \sqrt{(3-6)^2 + (1.25-0)^2} = \sqrt{9 + 1.5625} = \sqrt{10.5625} \approx 3.25 \]

Answer: The dump should be located at the Voronoi vertex (3, 1.25), which is 3.25 units from the nearest towns.

General Steps:

1. Plot all sites on coordinate plane
2. Connect sites to form triangulation (usually Delaunay)
3. Find midpoints of each edge connecting sites
4. Draw perpendicular bisectors through each midpoint
5. Identify intersections of perpendicular bisectors (vertices)
6. Connect vertices to form Voronoi edges
7. Extend edges to boundary or infinity as appropriate

IB Exam Context:

You will typically NOT be asked to construct a complete Voronoi diagram from scratch

Common exam tasks:

• Find equation of one missing edge (perpendicular bisector)
• Identify nearest site for a given point
• Add a new site and determine affected regions
• Find optimal location (toxic waste dump)
• Calculate distances to nearest neighbours

⚠️ Common Pitfalls & Tips:

• Use ruler for accurate perpendicular bisectors if drawing
• Label all sites clearly (A, B, C...)
• Mark vertices with dots where edges meet
• Remember edges extend infinitely unless bounded

Key Components

• Sites: Given points
• Cells: Regions around each site
• Edges: Perpendicular bisectors
• Vertices: Where edges meet

Main Problems

• Find missing edge equation
• Nearest neighbour identification
• Largest empty circle
• Adding new sites

Perpendicular Bisector

• Find midpoint
• Find gradient
• Perpendicular: \(-1/m\)
• Write equation

Toxic Waste Dump

• Check all vertices
• Calculate distances
• Find maximum minimum
• Use GDC for accuracy