Voronoi diagrams AI HL

IB Mathematics: Applications and Interpretation HL · Unit 3: Geometry and Trigonometry

Lesson 3.6 · Voronoi Diagrams

Nearest sites, boundaries, cells, vertices and the placement of a new site.

Faith connection

Psalm 66:1 calls everyone to worship: “Make a joyful noise unto God, all ye lands” (KJV). A Voronoi diagram divides a region according to nearby places, but the psalm’s invitation reaches across every region. Wherever you are today, you can praise God. Invite a friend or family member to join you in thanking him for his goodness.

Learning objectives

By the end of this lesson, you should be able to:

identify sites, cells, edges and vertices on a Voronoi diagram;
interpret each cell as the region nearest to its site;
use perpendicular bisectors to find equations of boundaries;
determine the site nearest to a given point;
explain how adding a site changes an existing diagram;
solve practical questions about service areas, region areas and locations far from existing sites.

1. What is a Voronoi diagram?

A site is a chosen point, such as a hospital, shop or weather station. Its Voronoi cell contains all locations at least as close to that site as to any other site. A boundary between two cells is called an edge. Where three or more cell boundaries meet, we have a vertex.

For this lesson, “distance” means straight-line distance on a flat map unless the question states otherwise. A road network can lead to different service regions.

Example with $A(1,1)$ , $B(5,1)$ and $C(5,5)$ . The three cells meet at $V(3,3)$ .

Boundary convention: A point inside one cell has one nearest site. A point on an edge is equally close to the two neighbouring sites. At a vertex, three or more sites can be equally close.

2. Why are the boundaries perpendicular bisectors?

Points equally distant from two sites $A$ and $B$ lie on the perpendicular bisector of $AB$ . The entire perpendicular bisector is a possible equal-distance line. Only the parts for which no other site is closer appear as edges in the final diagram.

Worked example · Two sites.

Let $A(1,2)$ and $B(7,2)$ . Their midpoint is $(4,2)$ . The segment $AB$ is horizontal, so its perpendicular bisector is:

$x=4$

To the left of $x=4$ , locations are closer to $A$ . To the right, they are closer to $B$ . On $x=4$ , distances to $A$ and $B$ are equal.

3. Construct a diagram with three sites

To construct a small Voronoi diagram:

Plot the sites accurately.
Find perpendicular bisectors for pairs of sites.
Find intersections of relevant bisectors.
Keep only the boundary portions that actually separate nearest-site regions.
Label each cell and check it contains its site.

Worked example · Three pharmacies.

Pharmacies are at $A(1,1)$ , $B(5,1)$ and $C(5,5)$ . The bisector between $A$ and $B$ is $x=3$ , while the bisector between $B$ and $C$ is $y=3$ .

For $A$ and $C$ , the midpoint is $(3,3)$ and segment $AC$ has gradient $1$ , so its perpendicular bisector is:

$y-3=-(x-3)\quad\Longrightarrow\quad x+y=6$

All three bisectors pass through the vertex $V(3,3)$ . The actual edges run from that vertex along the portions shown in the diagram: downward on $x=3$ , rightward on $y=3$ , and northwest on $x+y=6$ .

4. Find the nearest site to a point

On a clear diagram, identify the cell containing the point. With coordinates, compare squared distances; this avoids unnecessary square roots. The smallest squared distance identifies the closest site.

Worked example · A home and three pharmacies.

The pharmacies are $A(1,1)$ , $B(5,1)$ and $C(5,5)$ . A home is at $H(1,4)$ . Calculate:

$HA^2=(1-1)^2+(4-1)^2=9$

$HB^2=(1-5)^2+(4-1)^2=25$

$HC^2=(1-5)^2+(4-5)^2=17$

Since $9$ is the smallest, pharmacy $A$ is closest.

5. Add a new site

A new site claims the locations closer to it than to every existing site. To update a diagram, draw perpendicular bisectors between the new site and relevant old sites; keep the parts that become nearest-site boundaries. Some existing edges shorten or disappear.

Worked example · A fourth pharmacy.

Add pharmacy $D(3,5)$ to the previous arrangement. For the home $H(1,4)$ :

$HD^2=(1-3)^2+(4-5)^2=5$

Previously, $HA^2=9$ . Since $5<9$ , the new pharmacy $D$ is now closest to the home. This single comparison answers the question about the home; a full new diagram requires updating the surrounding cell boundaries as well.

6. Find an edge equation from two sites

Use midpoint and perpendicular gradient, as in Lesson 3.5. If additional sites are present, check whether the resulting line segment is genuinely an edge or whether another site is nearer along part of it.

Worked example · A sloping boundary.

Let $P(1,1)$ and $Q(5,3)$ . The midpoint is $(3,2)$ , and $PQ$ has gradient $(3-1)/(5-1)=1/2$ . The perpendicular bisector has gradient $-2$ :

$y-2=-2(x-3)$

$2x+y=8$

With only these two sites, the full line is their Voronoi edge. With more sites, only part of it may remain visible.

7. Area of a cell within a specified region

A Voronoi cell can extend without bound. If a question asks for its area, look for a finite study region, such as a rectangle representing the town. Find where the edges meet that region and calculate the resulting polygon’s area.

Worked example · Two service areas.

A rectangular town is represented by $0\leq x\leq10$ and $0\leq y\leq8$ , where each unit is $1$ km. Clinics lie at $A(2,4)$ and $B(8,4)$ . Their boundary is $x=5$ .

Within the town, clinic $A$ serves a rectangle of width $5$ km and height $8$ km:

$\text{area of A's cell}=5(8)=40\text{ km}^2$

Clinic $B$ serves the other $40$ km $^2$ . Locations exactly on the boundary are equally near both clinics.

8. Finding a point far from existing sites

In a question that specifies a finite set of eligible Voronoi vertices, evaluate each candidate’s distance to its nearest existing site. The vertex with the greatest such distance is the best candidate for placing a new site as far as possible from existing sites.

Check the wording carefully: if an entire bounded region is available and boundary locations are allowed, its boundary may also need consideration. Do not assume that a Voronoi vertex is automatically the best point without the question’s conditions.

Worked example · Compare candidate vertices.

At candidate vertex $P$ , the nearest existing site is $5$ km away. At candidate vertex $Q$ , the nearest site is $4.2$ km away. If the question restricts the choice to these two vertices, select $P$ : it has the larger nearest-site distance. A farther site elsewhere does not affect this comparison; the limiting site is the nearest one.

Exam and calculator tips

Keep site, cell, edge and vertex distinct.
An edge is part of a perpendicular bisector, not necessarily its entire line.
Squared distances give the same nearest-site ranking as actual distances.
When adding a site, check which old cells it takes territory from.
For areas, identify the boundary of the study region and include units squared.
For a proposed location far from existing sites, compare distances to its nearest site.

IB-style Paper 1 · Skill practice

Question 1 · Vocabulary

In a Voronoi diagram, what is represented by (a) a cell, (b) an edge and (c) a vertex?

Show solution

A cell contains locations closest to its site. An edge contains locations equally close to two neighbouring sites, with no other site closer. A vertex is where at least three edges meet and is typically equally distant from three or more sites.

Question 2 · Boundary equation

Sites $A(0,2)$ and $B(8,6)$ are given. Find the equation of their perpendicular bisector.

Show solution

The midpoint is $(4,4)$ . The gradient of $AB$ is $4/8=1/2$ , so the perpendicular gradient is $-2$ .

$y-4=-2(x-4)\quad\Longrightarrow\quad 2x+y=12$

Question 3 · Nearest site

Sites are $A(1,1)$ , $B(7,1)$ and $C(4,7)$ . Which site is closest to $P(4,3)$ ?

Show solution

$PA^2=3^2+2^2=13$ , $PB^2=(-3)^2+2^2=13$ , and $PC^2=0^2+(-4)^2=16$ . Thus $P$ is equally close to $A$ and $B$ and farther from $C$ . It lies on an edge between the cells of $A$ and $B$ .

Question 4 · A vertex

Three sites are $A(0,0)$ , $B(8,0)$ and $C(0,6)$ . Find the Voronoi vertex and its distance from each site.

Show solution

The bisector of $AB$ is $x=4$ and that of $AC$ is $y=3$ . They meet at $(4,3)$ , which is $\sqrt{4^2+3^2}=5$ units from each of the three sites.

Question 5 · Add a site

Sites $A(0,0)$ and $B(8,0)$ initially serve a region. A new site $C(4,3)$ is added. Determine the closest site to $P(4,2)$ before and after $C$ is added.

Show solution

Before $C$ is added, $PA^2=4^2+2^2=20$ and $PB^2=(-4)^2+2^2=20$ , so $P$ is tied between $A$ and $B$ . Afterward, $PC^2=(4-4)^2+(2-3)^2=1$ , so $C$ is uniquely closest.

Question 6 · Finite cell area

A rectangular district is $12$ km wide and $6$ km high. Two sites lie on its horizontal centreline, $4$ km apart, and their perpendicular bisector divides the district into two equal rectangles. Find the area of each service cell within the district.

Show solution

The district area is $12(6)=72$ km $^2$ . The bisector divides it equally, so each service cell has area $36$ km $^2$ .

Applications and interpretation

Application 1 · Pharmacies in a neighbourhood

Pharmacies are located at $A(1,1)$ , $B(5,1)$ and $C(5,5)$ on a square-coordinate map. A home is at $H(1,4)$ .

Find the Voronoi vertex for $A$ , $B$ and $C$ .
Identify the closest pharmacy to $H$ .
A new pharmacy $D(3,5)$ opens. Is it now closest to $H$ ?

Show solution

The bisectors $x=3$ and $y=3$ meet at $(3,3)$ , the Voronoi vertex. Initially, $HA^2=9$ , $HB^2=25$ and $HC^2=17$ , so $A$ is closest. After $D$ opens, $HD^2=(1-3)^2+(4-5)^2=5$ , so $D$ becomes closest.

Application 2 · A new health centre

Three villages are at $A(0,0)$ , $B(12,0)$ and $C(0,10)$ . A proposed health centre should be equally distant from all three.

Find its coordinates.
Find its straight-line distance from each village.
Explain one reason why this location might not minimise residents’ travel times.

Show solution

The perpendicular bisector of $AB$ is $x=6$ , and that of $AC$ is $y=5$ . The health centre is at $(6,5)$ , at distance $\sqrt{6^2+5^2}=\sqrt{61}\approx7.81$ map units from each village. Roads, rivers or hills may make travel times differ even where straight-line distances are equal.

Application 3 · Planning service regions

A rectangular service area is $0\leq x\leq14$ , $0\leq y\leq8$ , with distances measured in kilometres. Two stations are at $A(3,4)$ and $B(11,4)$ .

Find the boundary between their service cells.
Find the area served by each station within the rectangle.
Determine which station serves the point $(9,7)$ .

Show solution

The midpoint of $AB$ is $(7,4)$ ; since $AB$ is horizontal, the boundary is $x=7$ . Each cell is $7$ km wide and $8$ km high, with area $56$ km $^2$ . Since $(9,7)$ lies to the right of $x=7$ , station $B$ serves it.

Application 4 · Siting a shop at a Voronoi vertex

A map identifies two eligible Voronoi vertices, $P$ and $Q$ , for a new shop. At $P$ , the distance to its nearest existing shop is $\sqrt{13}$ km; at $Q$ , it is $\sqrt{11}$ km. The town permits the new shop only at one of these two vertices.

Which site should be selected to maximise distance to the nearest competitor?
How far is the selected site from its nearest existing shop, to three significant figures?
Give one additional practical factor the shop owner should consider.

Show solution

Select $P$ because $\sqrt{13}>\sqrt{11}$ . Its nearest existing shop is $\sqrt{13}\approx3.61$ km away. The owner might also consider customers’ locations, transport links, rents or site availability.

Paper 1 checklist

Label sites and cells. Use perpendicular bisectors for possible boundaries, then check which portions remain edges. Compare squared distances when identifying a nearest site. For an area or an optimum location, read the permitted region and candidate conditions carefully.

Lesson 3.6 · Voronoi Diagrams

Faith connection

Learning objectives

1. What is a Voronoi diagram?

2. Why are the boundaries perpendicular bisectors?

3. Construct a diagram with three sites

4. Find the nearest site to a point

5. Add a new site

6. Find an edge equation from two sites

7. Area of a cell within a specified region

8. Finding a point far from existing sites

Exam and calculator tips

IB-style Paper 1 · Skill practice

Question 1 · Vocabulary

Question 2 · Boundary equation

Question 3 · Nearest site

Question 4 · A vertex

Question 5 · Add a site

Question 6 · Finite cell area

Applications and interpretation

Application 1 · Pharmacies in a neighbourhood

Application 2 · A new health centre

Application 3 · Planning service regions

Application 4 · Siting a shop at a Voronoi vertex

Paper 1 checklist

Related

Company

Links

Support

Recommend

alphy school publishers

IB Mathematics: Applications and Interpretation HL 6 Sections80 LessonsLifetime

Curriculum

Voronoi diagrams AI HL

Faith connection

Learning objectives

1. What is a Voronoi diagram?

2. Why are the boundaries perpendicular bisectors?

3. Construct a diagram with three sites

4. Find the nearest site to a point

5. Add a new site

6. Find an edge equation from two sites

7. Area of a cell within a specified region

8. Finding a point far from existing sites

Exam and calculator tips

IB-style Paper 1 · Skill practice

Question 1 · Vocabulary

Question 2 · Boundary equation

Question 3 · Nearest site

Question 4 · A vertex

Question 5 · Add a site

Question 6 · Finite cell area

Applications and interpretation

Application 1 · Pharmacies in a neighbourhood

Application 2 · A new health centre

Application 3 · Planning service regions

Application 4 · Siting a shop at a Voronoi vertex

Paper 1 checklist

Related

Leave A Reply Cancel reply

Company

Links

Support

Recommend

alphy school publishers

Customise Consent Preferences

Log in with your account

Modal title