Voronoi Construction (AI HL)

The boundary between two sites in a Voronoi diagram lies on the perpendicular bisector of the line joining them, and a vertex is where three bisectors meet. To construct these, find the midpoint of the two sites, use the negative reciprocal of their gradient, and solve pairs of bisector equations simultaneously. Questions give site coordinates, so the construction is algebraic rather than a drawing. It's part of the broader Voronoi Diagrams topic.

16 questions on this sub-topic.

Syllabus

CodeSyllabus content
SL3.6Voronoi diagrams: sites, vertices, edges and cells. Addition of a site to an existing Voronoi diagram. Nearest neighbour interpolation. Applications of the "toxic waste dump" problem. Site coordinates are given in exams for calculating the perpendicular bisector equations - you are not required to physically construct the diagram. Questions may ask for the equation of a boundary, the site closest to a given point, or the area of a region.

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

Skills practised on this page:

Key formula

Perpendicular bisector between two sites

Find the midpoint of the two sites and the negative reciprocal of the gradient between them, then write the line through that midpoint with that gradient. This line is the shared edge of the two sites' cells.

Not in the formula booklet - coordinate geometry

Finding a Voronoi vertex

Solve two bisector equations simultaneously - the intersection is equidistant from all three sites involved, and is always where exactly three edges meet in exam questions.

Not in the formula booklet - simultaneous equations

Need the full syllabus wording and formula reference table? See Voronoi Diagrams.

Key terms

What is a perpendicular bisector?

The perpendicular bisector of two sites is the line through their midpoint at right angles to the line joining them. Every point on it is the same distance from both sites.

e.g. For A(0,0)A(0,0) and B(4,2)B(4,2), the midpoint is (2,1)(2,1) and the gradient of ABAB is 12\dfrac12, so the bisector has gradient −2-2 and equation y=−2x+5y=-2x+5.

How do you find the midpoint of two sites?

Add the xx-coordinates and halve the result, then do the same for the yy-coordinates. Both coordinates must be averaged.

e.g. The midpoint of (3,−1)(3,-1) and (7,5)(7,5) is (3+72,−1+52)=(5,2)\left(\dfrac{3+7}{2},\dfrac{-1+5}{2}\right)=(5,2).

How do you find the gradient of a bisector?

Find the gradient mm between the two sites, then use the negative reciprocal −1m-\dfrac1m. If the sites share the same yy-coordinate the bisector is vertical, and if they share the same xx-coordinate it is horizontal.

e.g. If the gradient between two sites is 23\dfrac23, the bisector has gradient −32-\dfrac32, since 23×(−32)=−1\dfrac23\times\left(-\dfrac32\right)=-1.

What is a Voronoi vertex?

A Voronoi vertex is a point where three cell edges meet. It lies on two bisectors at once, so it is found by solving their equations simultaneously.

e.g. For sites (0,0)(0,0), (4,0)(4,0) and (0,4)(0,4), the bisectors x=2x=2 and y=2y=2 meet at the vertex (2,2)(2,2).

Worked examples

1
Easy
GDC
[4 marks]

Find the perpendicular bisector of A(2,3)A(2, 3) and B(2,9).B(2, 9).

Worked solution

The segment is vertical, M1
so the bisector is horizontal A1
through the midpoint (2,6)(2, 6): M1
y=6.y = 6. A1On the GDC. Solve (x−3)2=(x−9)2(x-3)^{2}=(x-9)^{2} for the solution near x=6x=6. The calculator shows about 6.

TI-84 Plus CE: math ▲ C:Numeric Solver E1 (x-3)^2 E2 (x-9)^2 OK, X = 6 alpha enterCasio fx-CG50: MENU Equation F3 type (x-3)^2=(x-9)^2 EXE X = 6 EXE ▲ F6Casio fx-CG100: HOME Equation Type tab Solver OK Eq line (x-3)^2=(x-9)^2 OK start estimate 6 Execute OKTI-Nspire CX: menu Algebra Numerical Solve (x-3)^2=(x-9)^2,x=6 enterFull GDC guide: Solve an equation numerically Topic page

M1 Vertical segment A1 Horizontal bisector M1 Midpoint A1 y=6y=6
2
Hard
GDC
[4 marks]

Find the point equidistant from the three sites A(0,0)A(0,0), B(6,0)B(6,0) and C(0,4)C(0,4).

-11234567-1123450ABCxy

Worked solution

Equidistant from A,BA, B: bisector xx M1
x=3.x = 3. A1
Equidistant from A,CA, C: bisector yy M1
y=2,y = 2, so the vertex is (3,2).(3, 2). A1On the GDC. Solve x2=(x−6)2x^{2}=(x-6)^{2} for the solution near x=3x=3. Solve x2=(x−4)2x^{2}=(x-4)^{2} for the solution near x=2x=2.

TI-84 Plus CE: math ▲ C:Numeric Solver E1 x^2 E2 (x-6)^2 OK, X = 3 alpha enter then math ▲ C:Numeric Solver E1 x^2 E2 (x-4)^2 OK, X = 2 alpha enterCasio fx-CG50: MENU Equation F3 type x^2=(x-6)^2 EXE X = 3 EXE ▲ F6 then MENU Equation F3 type x^2=(x-4)^2 EXE X = 2 EXE ▲ F6Casio fx-CG100: HOME Equation Type tab Solver OK Eq line x^2=(x-6)^2 OK start estimate 3 Execute OK then HOME Equation Type tab Solver OK Eq line x^2=(x-4)^2 OK start estimate 2 Execute OKTI-Nspire CX: menu Algebra Numerical Solve x^2=(x-6)^2,x=3 enter then menu Algebra Numerical Solve x^2=(x-4)^2,x=2 enterFull GDC guide: Solve an equation numerically Topic page

M1 Bisector of AB A1 x=3x=3 M1 Bisector of AC A1 y=2y=2
3
Medium
GDC
[5 marks]

Find the perpendicular bisector of A(−2,4)A(-2, 4) and B(4,−2).B(4, -2).

Worked solution

Midpoint (1,1).(1, 1). M1
Midpoint (1,1).(1, 1). A1
Gradient AB=−1AB = -1, bisector gradient =1.= 1. M1
Bisector gradient =1.= 1. A1
y=x.y = x. A1

Solve on the GDC - graph each side and use intersect, or an equation solver (TI‑84 PlySmlt2 / Solver · Casio EQUA · Nspire solve()).

M1 Midpoint A1 (1,1)(1,1) M1 Perpendicular gradient A1 Correct answer of 11 A1 Equation

Common mistakes

  • Using the gradient between the sites instead of its negative reciprocal. A bisector is perpendicular to the segment joining the two sites, so the gradient must be flipped and inverted - reusing the original gradient is the single most common slip in these questions.
  • Averaging only one coordinate when finding the midpoint. The midpoint needs both (x1+x22,y1+y22)\left(\frac{x_1+x_2}{2}, \frac{y_1+y_2}{2}\right) coordinates averaged separately - dropping one and copying the other across gives a point that isn't on the bisector at all.
  • Stopping after finding one bisector when a vertex is asked for. A Voronoi vertex needs two bisector equations solved simultaneously - a single bisector only gives an edge, not the point where three cells meet.

Quick questions

How do I find the perpendicular bisector between two sites?

Find the midpoint of the two sites and the negative reciprocal of the gradient between them, then write the equation of the line through that midpoint with that gradient.

How do I find a Voronoi vertex from bisector equations?

Solve two bisector equations simultaneously. Their intersection is equidistant from all three sites involved, and in exam questions it is always the point where exactly three edges meet.

What is the bisector when the two sites have the same xx-coordinate?

It is a horizontal line through the midpoint, so its equation is yy equal to a constant. For sites (5,1)(5,1) and (5,7)(5,7), the midpoint is (5,4)(5,4) and the bisector is y=4y=4.

How can I check my perpendicular bisector is correct?

Pick a point on the line and check that it is the same distance from both sites. For sites (1,1)(1,1) and (5,3)(5,3), the bisector y=−2x+8y=-2x+8 contains (4,0)(4,0), which is 10\sqrt{10} from both sites.

Why is a Voronoi vertex the same distance from all three sites?

A point on the bisector of sites AA and BB is equally far from both, and a point on the bisector of BB and CC is equally far from both. The intersection lies on both lines, so its distances to AA, BB and CC are all equal.

Ready to practise properly?

16 Voronoi-construction questions, marked instantly like the real exam.