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.
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:
Steps to add a site to a Voronoi diagram: