Voronoi diagrams AI SL

A Voronoi diagram splits a region into cells, one for each site, so that every point in a cell is closer to its own site than to any other site. Each edge is part of a perpendicular bisector of two sites, and a vertex, where three edges meet, is a point equally far from three sites. This page shows how to find the equation of an edge from the coordinates of two sites, decide which site is nearest to a point, and find a vertex with your calculator, which is how the problem of placing something as far as possible from every site is solved.

Formulas at a glance

There is no formula for Voronoi diagrams in the booklet, but the tools you use are there: the equation of a straight line, the gradient formula, and the formulas for distance and midpoint. The condition that perpendicular gradients multiply to give −1-1 is not in the booklet, so learn it.

Midpoint of a segment

M=(x1+x22,y1+y22)M=\left(\dfrac{x_1+x_2}{2},\dfrac{y_1+y_2}{2}\right)

In the booklet

Gradient between two points

m=y2−y1x2−x1m=\dfrac{y_2-y_1}{x_2-x_1}

In the booklet

Equation of a line through a point

y−y1=m(x−x1)y-y_1=m(x-x_1)

In the booklet

Test for perpendicular lines

m1×m2=−1m_1\times m_2=-1

Not in the booklet

Which method to use

Most Voronoi questions come down to finding a boundary, deciding which site is nearest, finding the point where three cells meet, or finding the area of a cell. Pick the job first, then the tool.

The question hasUseNotes
The boundary between the cells of two sitesThe midpoint of the two sites and the negative reciprocal of the gradient joining them, then y−y1=m(x−x1)y-y_1=m(x-x_1)Every point on the edge is equally far from the two sites
Which site is nearest to a given pointWork out the distance, or the squared distance, from the point to each site and choose the smallestSquared distances avoid square roots and give the same order
Whether a point lies on a boundaryCheck that its distances to the two sites are equal, or that it satisfies the equation of the edgeA point not on the edge lies in the cell of the nearer site
The vertex where three cells meetSolve the equations of two edges together with the calculatorThe third edge passes through the same point, which is a useful check
A place as far as possible from every site, as in the toxic waste dump problemThe Voronoi vertexIn examinations the solution is always where three edges meet
A value, such as rainfall, estimated at a pointNearest neighbour interpolation: use the value of the site whose cell contains the pointFind which cell the point is in first
A new site added to a diagramFind the bisectors between the new site and its neighbours; they cut out the new cellThe cells of the neighbouring sites become smaller
The area of a cellFind its vertices (edge intersections and the corners of the region), then split it into triangles or rectangles and addSketch the cell first and label every vertex

SL3.5 SL3.6

Voronoi diagrams

A Voronoi diagram divides a plane into cells, one for each site, so that every point in a cell is closer to its own site than to any other site. The boundaries between cells lie along perpendicular bisectors of pairs of sites. Use a diagram to find the nearest site to a point, or to find a vertex, which is equally far from three sites.

The key techniques

In examinations you're given the coordinates of the sites - you are never asked to construct perpendicular bisectors by hand.

Voronoi edge

y−y1=m⊥(x−x1)y-y_1=m_\perp(x-x_1)

Through the midpoint of two sites, using the perpendicular gradient m⊥=−1mm_\perp=-\dfrac{1}{m}. Every point on this line is equidistant from both sites.

Not a separate booklet formula - built from the midpoint, the gradient and the point-gradient form, which are all in the booklet

Squared-distance test

Compare PA2PA^2 and PB2PB^2

To decide which cell a point PP belongs to, compare squared distances to each site rather than the distances themselves - it avoids unnecessary square roots and the smaller value wins.

Not a separate booklet formula - direct use of the distance formula, which is in the booklet

Key terms

What is a site?

A site is one of the given points, such as a shop or a transmitter, that a cell is built around. Each site lies inside its own cell.

e.g. For shops at P(2,3)P(2,3) and Q(6,7)Q(6,7), the two sites are PP and QQ, and the diagram has two cells.

What is a cell?

A cell is the region of all points that are closer to one site than to any other site.

e.g. A point in the cell of site AA is closer to AA than to BB or CC.

What are edges and vertices?

An edge is a boundary between two cells and is part of a perpendicular bisector. A vertex is a point where three edges meet, so it is equally far from three sites.

e.g. The point (3,4)(3,4) is a vertex for sites (0,0)(0,0), (6,0)(6,0) and (0,8)(0,8), because it is distance 55 from each.

How do you decide which site is nearest to a point?

Work out the distance, or the squared distance, from the point to each site and choose the smallest. Comparing squared distances avoids square roots.

e.g. For the point (1,1)(1,1) and sites (0,0)(0,0) and (4,0)(4,0), the squared distances are 22 and 1010, so (0,0)(0,0) is nearer.

How do you find the area of a cell?

Find the vertices of the cell, which are where its edges meet each other and the border of the region, sketch the cell, then split it into rectangles and triangles and add their areas.

e.g. A region is 0≤x≤120\le x\le12, 0≤y≤50\le y\le5, with sites U(2,2)U(2,2) and V(10,2)V(10,2). The edge between them is x=6x=6, so the cell of UU has corners (0,0)(0,0), (6,0)(6,0), (6,5)(6,5) and (0,5)(0,5). It is a 66 by 55 rectangle, so its area is 3030.

Worked example, step by step

The question Calculator needed for the vertex [7 marks]

Three weather stations are at P(1,1)P(1,1), Q(9,3)Q(9,3) and R(3,9)R(3,9), with coordinates in kilometres. Each station is a site of a Voronoi diagram.

(a) Find the equation of the perpendicular bisector of PQPQ, in the form y=mx+cy=mx+c.

(b) The perpendicular bisector of PRPR has equation y=−0.25x+5.5y=-0.25x+5.5. Find the coordinates of the Voronoi vertex where the three cells meet.

Worked solution: worked example

Answer: (a) y=−4x+22y=-4x+22 (b) (4.4, 4.4)(4.4,\ 4.4)

Step 1 - Find the midpoint of PQ.

M=(1+92, 1+32)=(5, 2).M=\left(\frac{1+9}{2},\ \frac{1+3}{2}\right)=(5,\ 2). A1 - (5,2)(5,2)

Why? The perpendicular bisector cuts the segment in half, so it passes through the midpoint. This gives one point on the edge.

Step 2 - Find the perpendicular gradient.

The gradient of PQPQ is 3−19−1=14,\frac{3-1}{9-1}=\frac14, so the gradient of the edge is the negative reciprocal, −4-4. M1 - Negative reciprocal of the gradient of PQPQ A1 - −4-4

Why? The edge meets PQPQ at a right angle, so its gradient multiplies with 14\tfrac14 to give −1-1. Check: 14×(−4)=−1\tfrac14\times(-4)=-1.

Step 3 - Write the equation of the edge.

Use y−y1=m(x−x1)y-y_1=m(x-x_1) with (5,2)(5,2) and m=−4m=-4: y−2=−4(x−5),y=−4x+22.y-2=-4(x-5),\quad y=-4x+22. M1 - Substitute the midpoint and −4-4 into a line equation A1 - y=−4x+22y=-4x+22

Why? The point-gradient form gives the equation straight away, without a separate step to find cc. Rearrange to y=mx+cy=mx+c because that is the form asked for.

Step 4 - Find the vertex with the calculator.

The vertex lies on both edges, so solve y=−4x+22y=-4x+22 and y=−0.25x+5.5y=-0.25x+5.5 together. Graph both lines and use the intersection tool, or write them as 4x+y=224x+y=22 and x+4y=22x+4y=22 and use the simultaneous equation solver. The calculator gives x=4.4x=4.4 and y=4.4y=4.4, so the vertex is (4.4, 4.4)(4.4,\ 4.4). M1 - Attempt to solve the two edge equations together with technology (implied by a correct answer) A1 - (4.4, 4.4)(4.4,\ 4.4)

Why? A vertex is where edges meet, so its coordinates must satisfy the equations of both of them. The calculator is quicker and safer than solving by hand.

Step 5 - Check the vertex.

The distances from V(4.4,4.4)V(4.4,4.4) are VP=3.42+3.42=4.81VP=\sqrt{3.4^2+3.4^2}=4.81, VQ=4.62+1.42=4.81VQ=\sqrt{4.6^2+1.4^2}=4.81 and VR=1.42+4.62=4.81VR=\sqrt{1.4^2+4.6^2}=4.81 kilometres. All three are equal, as they must be. This is also the best place for something that must be as far as possible from all three stations, which is the toxic waste dump problem.

Why? A vertex is equally far from the three sites around it, so equal distances show the point is right. Moving away from the vertex in any direction brings you closer to at least one site.

Marks (7):
A1 (5,2)(5,2)
M1 Negative reciprocal of the gradient of PQPQ
A1 −4-4
M1 Substitute the midpoint and −4-4 into a line equation
A1 y=−4x+22y=-4x+22
M1 Attempt to solve the two edge equations together with technology (implied by a correct answer)
A1 (4.4, 4.4)(4.4,\ 4.4)

Now you try: enter your answers to be marked

These are real practice questions. Type your answer in each box and press Mark it. The worked solution and mark scheme appear straight away, and your first attempt is the one that counts. Use the keyboard for powers, roots and trig, and the working box for your notes.

1
Easy
Calculator
[2 marks]
Two shops are at A(2,0)A(2,0) and B(10,0)B(10,0).

Find the point on the xx-axis equidistant from both.
[2]
Fractions & powers
Other

Worked solution: practice question 1

2
Medium
Calculator
[2 marks]
Hospitals are at H1(1,1), H2(7,3), H3(3,8).H_1(1, 1),\ H_2(7, 3),\ H_3(3, 8). An accident occurs at X(4,4).X(4, 4). Find the nearest hospital using squared distances.
[2]
Fractions & powers
Other

Worked solution: practice question 2

3
Medium
Calculator
[5 marks]
Two cafés are at A(2,3)A(2, 3) and B(8,7).B(8, 7). The boundary between regions closest to each is the perpendicular bisector of AB.AB. Find its equation.
[5]
Fractions & powers
Other

Worked solution: practice question 3

Your score so far: 0 out of 9 marks

Common mistakes

  • Assuming a Voronoi cell boundary is curved. Every edge in a Voronoi diagram is a straight line - a segment of a perpendicular bisector - never an arc.
  • Not checking the vertex. A Voronoi vertex is equidistant from three sites. Two edges are enough to find it; checking the third edge, or the three equal distances, catches a slip.
  • Trying to construct the diagram by hand. Exam questions give you the coordinates of the sites and expect an algebraic answer - midpoint, then perpendicular gradient - not a compass-and-ruler sketch, which is both unnecessary and too imprecise to mark.

Try some questions on Voronoi diagrams

Using your GDC

The exact key presses for the TI-84 Plus CE, Casio fx-CG50, Casio fx-CG100 and TI-Nspire CX, with what the screen shows. Pick your calculator.

Solve a system of equations

Used in: Voronoi diagrams

How to solve a system of equations on a TI-84 Plus CE

Simultaneous Equation Solver app (PlySmlt2)

Press apps and choose PlySmlt2. An information screen appears: press any key to reach the MAIN MENU, then choose Simultaneous Eqn Solver.

On the mode screen choose 3 equations and 3 unknowns. Choose Dec instead of Auto if you want decimal answers rather than fractions. Choose NEXT, using the key directly below it on the screen.

Equations: 3
Unknowns: 3

Enter the coefficients row by row, one row for each equation, with the constant (the number on the right of the equals sign) last. Press enter after each number to move to the next position. For a negative number use (−), not the subtraction key. Write each equation as ax+by+cz=dax + by + cz = d first: a missing term has coefficient 0.

1  2  3  10
2  -1  1  3
3  1  -2  1

Choose SOLVE, using the key directly below it on the screen. The solution for each unknown is shown.

x=6/5x = 6/5, y=7/5y = 7/5 and z=2z = 2, which is x=1.2x = 1.2, y=1.4y = 1.4 and z=2z = 2 in decimal form.

x1=6/5
x2=7/5
x3=2

If the system has no solution or infinitely many solutions, the app does not show a single answer. The rref choice then shows the reduced row-echelon form, where a row of zeros followed by a non-zero number means no solution. To leave the app, go to the main menu and choose Quit App.

Check each solution by substituting it back into one of the original equations, in case a coefficient was typed in the wrong place.

The full guide: Solve a system of equations

Find where two graphs meet (intersection)

Used in: Voronoi diagrams

How to find where two graphs meet on a TI-84 Plus CE

Graph both and use intersect

Press Y=, clear any old functions with clear, then type X,T,θ,n x² − 3 next to Y1=. Press ▼ and type 2 X,T,θ,n + 1 next to Y2=.

Plot1 Plot2 Plot3
\Y1=X²-3
\Y2=2X+1
\Y3=

Press window and set Xmin = −3, Xmax = 5, Ymin = −4, Ymax = 10. For a negative number use the (−) key, not the subtraction key. Press graph. Both curves should show, with two crossing points on the screen.

WINDOW
Xmin=-3
Xmax=5
Xscl=1
Ymin=-4
Ymax=10
Yscl=1

Press 2nd trace (CALC) and choose 5:intersect. First curve? appears with the cursor on one graph: press enter. Second curve? appears: press enter again. If more than two graphs are drawn, use ▲ or ▼ to put the cursor on the right graph before pressing enter.

Second curve?

Guess? appears. Use ◀ or ▶ to move the cursor close to the right-hand crossing, then press enter.

The screen shows Intersection with x=3.24x = 3.24 and y=7.47y = 7.47.

Intersection X=3.236068 Y=7.472136

For the other crossing, repeat 2nd trace 5:intersect, enter, enter, and this time move the guess close to the left-hand crossing before pressing enter.

x=−1.24x = -1.24 and y=−1.47y = -1.47.

Intersection X=-1.236068 Y=-1.472136

The guess decides which crossing the calculator finds, so give a guess near the point you want. A crossing outside the window cannot be found, so check WINDOW first.

The full guide: Find where two graphs meet (intersection)

Enter a calculation on the home screen

Used in: Voronoi diagrams

How to enter a calculation on a TI-84 Plus CE

Type a calculation and press enter

Go to the home screen: press 2nd mode (QUIT) from any menu or app. Press clear if the entry line is not empty.

Type the calculation as you would write it, then press enter. For 3(2.4)2−5×1.83(2.4)^2 - 5 \times 1.8 press 3 ( 2 . 4 ) x² − 5 × 1 . 8 enter.

The calculator understands a number next to a bracket as a multiplication, so × is not needed in 3(2.4)3(2.4). If a fraction, square root or power template is on the screen, press ▶ to move out of it before you carry on typing.

8.288.28

3(2.4)²-5*1.8
8.28
Use the last answer in the next calculation

To increase the answer by 15%, press × 1 . 1 5 enter on a blank line. The calculator puts Ans, the last answer, in front of the operator for you.

You can also type Ans yourself, anywhere in a calculation: press 2nd (−) (ANS), for example 2nd (−) (ANS) × 1 . 1 5 enter.

9.5229.522, which is 9.529.52 to 3 significant figures.

Ans*1.15
9.522

To use an earlier entry or answer, press ▲ to move up through the history, then enter to paste the highlighted one on the entry line. Press 2nd enter (ENTRY) to bring back your last entry and change it.

Ans always holds the last answer that was worked out, so if you do a different calculation in between, Ans changes. Type a number you need later, or keep it on the screen, rather than relying on Ans for many steps.

The full guide: Enter a calculation on the home screen

See the full list of GDC guides for every calculator task.

Syllabus content covered

CodeSyllabus content
SL3.5Equations of perpendicular bisectors, given either two points, or the equation of a line segment and its midpoint.
SL3.6Voronoi diagrams: sites, vertices, edges, cells. Addition of a site to an existing Voronoi diagram. Nearest neighbour interpolation. Applications of the "toxic waste dump" problem. In examinations, coordinates of sites for calculating the perpendicular bisector equations will be given. Students will not be required to construct perpendicular bisectors. Questions may include finding the equation of a boundary, identifying the site closest to a given point, or calculating the area of a region. In examinations, the solution point will always be at an intersection of three edges.

Official IB source: Mathematics: applications and interpretation subject brief (PDF, ibo.org).

Quick questions

What is a Voronoi diagram?

A Voronoi diagram divides the plane into cells around a set of sites, so every point in a cell is closer to that cell's site than to any other. Edges are segments of perpendicular bisectors, and a vertex is where three edges meet.

How do you find the edge between two Voronoi sites?

Find the midpoint of the two sites, then find the gradient perpendicular to the segment joining them (the negative reciprocal of its gradient). The line through the midpoint with that gradient is the Voronoi edge.

What does nearest-neighbour interpolation mean?

It estimates a value at a point by using the value of the nearest site, so every point in a cell takes the value of that cell's site. For example, the temperature at a point can be taken from the nearest weather station.

What happens to a Voronoi diagram when a new site is added?

The new site gets its own cell, found from the perpendicular bisectors between it and its neighbouring sites. Nearby cells shrink, and some of their edges are shortened or replaced.

How do I solve the toxic waste dump problem?

The dump should be as far as possible from the nearest site, and in these problems the answer is a Voronoi vertex, where three edges meet. Find the vertex by solving two bisector equations together, then check its distance to the sites.

Ready to practise properly?

Practice questions on every section, marked instantly like the real exam.