13.03 Constructing Voronoi diagrams

As previously taught, the perpendicular bisector of a line segment  $AB$AB, is a line that is equidistant to point $A$A and point $B$B. Therefore, we can use this concept to find the equations of the edges between sites on a Voronoi diagram, as each point on the edges needs to be equidistant between the two sites. To find the vertices on the Voronoi diagram, we then need to find the intercepts of these edges.

Worked examples

example 1

Construct a Voronoi diagram for the sites $A(-2,5)$A(−2,5) and $B(4,-1)$B(4,−1). 

Think: Because there are only two sites, we just need to find one edge, which is the perpendicular bisector of the line segment $AB$AB.  This also means that there will be no vertices on the Voronoi diagram. 

Do: Let's find the equation of the perpendicular bisector of $AB$AB by first finding the midpoint between the two sites:

Midpoint	$=$=	$\left(\frac{-2+4}{2},\frac{5+(-1)}{2}\right)$(−2+42​,5+(−1)2​)
	$=$=	$\left(1,2\right)$(1,2)

Now we should find the gradient of $AB$AB: 

$m_1$m1​	$=$=	$\frac{-1-5}{4-(-2)}$−1−54−(−2)​
	$=$=	$\frac{-6}{6}$−66​
	$=$=	$-1$−1

Therefore the gradient of the perpendicular bisector is the negative reciprocal which is $1$1. Now we can find the equation of the perpendicular bisector using the point-gradient formula of a line:

$y-y_1$y−y1​	$=$=	$m(x-x_1)$m(x−x1​)
$y-2$y−2	$=$=	$1(x-1)$1(x−1)
$y$y	$=$=	$x+1$x+1

 

So this is the equation of the edge on our Voronoi diagram. So to construct the Voronoi diagram, we must sketch this straight line and plot the two sites $A(-2,5)$A(−2,5) and $B(4,-1)$B(4,−1)  on a number plane:

Example 2

Construct a Voronoi diagram for the sites $A(-4,0),$A(−4,0), $B(2,3)$B(2,3) and $C(5,-4)$C(5,−4). 

Do: Let's find the equation of the perpendicular bisector of $AB$AB by first finding the midpoint between the two sites $A(-4,0),$A(−4,0), and $B(2,3)$B(2,3):

Midpoint	$=$=	$\left(\frac{-4+2}{2},\frac{0+3}{2}\right)$(−4+22​,0+32​)
	$=$=	$\left(-1,1.5\right)$(−1,1.5)

Now we should find the gradient of $AB$AB: 

$m_1$m1​	$=$=	$\frac{0-3}{-4-2}$0−3−4−2​
	$=$=	$\frac{-3}{-6}$−3−6​
	$=$=	$\frac{1}{2}$12​

Therefore the gradient of the perpendicular bisector is the negative reciprocal which is $-2$−2. Now we can find the equation of the perpendicular bisector using the point-gradient formula of a line:

$y-y_1$y−y1​	$=$=	$m(x-x_1)$m(x−x1​)
$y-\frac{3}{2}$y−32​	$=$=	$-2(x+1)$−2(x+1)
$y$y	$=$=	$-2x-\frac{1}{2}$−2x−12​

 

So this is the equation of the edge between  the regions for the two sites $A(-2,5)$A(−2,5) and $B(4,-1)$B(4,−1)  on our Voronoi diagram.

Now let's find the equation of the perpendicular bisector of sites $B(2,3)$B(2,3) and $C(5,-4)$C(5,−4):

Midpoint	$=$=	$\left(\frac{2+5}{2},\frac{3-4}{2}\right)$(2+52​,3−42​)
	$=$=	$\left(3.5,-0.5\right)$(3.5,−0.5)

Now we should find the gradient of $BC$BC: 

$m_1$m1​	$=$=	$\frac{-4-3}{5-2}$−4−35−2​
	$=$=	$\frac{-7}{3}$−73​

Therefore the gradient of the perpendicular bisector is the negative reciprocal which is $\frac{3}{7}$37​. Now we can find the equation of the perpendicular bisector using the point-gradient formula of a line:

$y-y_1$y−y1​	$=$=	$m(x-x_1)$m(x−x1​)
$y+\frac{1}{2}$y+12​	$=$=	$\frac{3}{7}\left(x-\frac{7}{2}\right)$37​(x−72​)
$y$y	$=$=	$\frac{3x}{7}-\frac{3}{2}-\frac{1}{2}$3x7​−32​−12​
$y$y	$=$=	$\frac{3x}{7}-2$3x7​−2

 

So this is the equation of the edge between  the regions for the two sites $B(2,3)$B(2,3) and $C(5,-4)$C(5,−4)  on our Voronoi diagram.

Now let's find the equation of the perpendicular bisector of $AC$AC by first finding the midpoint between the two sites $A(-4,0)$A(−4,0) and $C(5,-4)$C(5,−4):

Midpoint	$=$=	$\left(\frac{-4+5}{2},\frac{0-4}{2}\right)$(−4+52​,0−42​)
	$=$=	$\left(0.5,-2\right)$(0.5,−2)

Now we should find the gradient of $AC$AC: 

$m_1$m1​	$=$=	$\frac{-4-0}{5-(-4)}$−4−05−(−4)​
	$=$=	$\frac{-4}{9}$−49​

Therefore the gradient of the perpendicular bisector is the negative reciprocal which is $\frac{9}{4}$94​. Now we can find the equation of the perpendicular bisector using the point-gradient formula of a line:

$y-y_1$y−y1​	$=$=	$m(x-x_1)$m(x−x1​)
$y+2$y+2	$=$=	$\frac{9}{4}\left(x-\frac{1}{2}\right)$94​(x−12​)
$y$y	$=$=	$\frac{9x}{4}-\frac{9}{8}-2$9x4​−98​−2
$y$y	$=$=	$\frac{9x}{4}-\frac{25}{8}$9x4​−258​

 

So this is the equation of the edge between  the regions for the two sites $A(-4,0)$A(−4,0) and $C(5,-4)$C(5,−4)  on our Voronoi diagram.

Now we can plot all the perpendicular bisectors and sites on a number plane. At first, plot the perpendicular bisectors as dashed lines (or in pencil):

Then trace over the lines that divide the regions appropriately with solid lines and delete the rest of the dashed lines: