13.04 Adding a site to a Voronoi diagram

Real-life applications of Voronoi diagrams, such as city planning, will change over time as sites will need to be adding as a city grows or requires more resources, such as train stations, public schools, petrol stations, etc. To add a site to a Voronoi diagram, we will need to create an appropriate cell for that site, which will change the edges in the original Voronoi diagram. 

 

Worked example

example 1

Add the site $C(4,4)$C(4,4) to the following Voronoi diagram: 

Do: First we should plot point $C$C so that we can see which cell it is in, so we know what edges need to be added. 

We can see that we need an edge between sites $B$B and $C$C since they are in the same cell. So we need to  find the perpendicular bisector of $BC$BC. Since $BC$BC is a vertical line, the perpendicular bisector will be a horizontal line through the midpoint $\left(4,\frac{3}{2}\right)$(4,32​) which is $y=\frac{3}{2}$y=32​. So let's add this line to our Voronoi diagram: 

We do not need the part of the line $y=\frac{3}{2}$y=32​  that is to the left of the original edge, so we can delete that to get the following diagram:

The edge between sites $A\left(-2,5\right)$A(−2,5) and $C\left(4,4\right)$C(4,4) in the top half of the diagram is clearly closer to site $C$C than $A$A. So we now need to find the perpendicular bisector of $AC$AC:

Midpoint	$=$=	$\left(1,\frac{9}{2}\right)$(1,92​)	Midpoint of $AC$AC
$m_{AC}$mAC​	$=$=	$-\frac{1}{6}$−16​	Gradient of $AC$AC
$m_2$m2​	$=$=	$6$6	Gradient of perpendicular bisector
$y-\frac{9}{2}$y−92​	$=$=	$6(x-1)$6(x−1)	Use point-gradient formula to find equation
$y$y	$=$=	$6x-6+\frac{9}{2}$6x−6+92​
$y$y	$=$=	$6x-\frac{3}{2}$6x−32​

 

Now we can add this perpendicular bisector to our Voronoi diagram:

We can see that the green line between $A$A and $C$C above the point of intersection can be deleted, and the blue line below the intersection can be deleted to get the following final Voronoi diagram: