topic badge
Standard level

13.04 Adding a site to a Voronoi diagram

Lesson

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}$y92 $=$= $6(x-1)$6(x1)

Use point-gradient formula to find equation

$y$y $=$= $6x-6+\frac{9}{2}$6x6+92

 

$y$y $=$= $6x-\frac{3}{2}$6x32

 

 

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:

Remember!

Steps to add a site to a Voronoi diagram:

  1. Plot the new site on your diagram.
  2. Find and plot the perpendicular bisector of the line segment between the two points that are in the same cell.
  3. Find and plot the perpendicular bisectors of the line segments joining the new site and any other sites in adjacent cells.
  4. Remove any edges that are unnecessary for the Voronoi diagram.

What is Mathspace

About Mathspace