Menu
Sign up Sign in

AI HL · 12.8

Voronoi Diagrams

0 of 19 skills done

0
12.8.4

Adding a site: the incremental algorithm

12.8.4

Adding a site: the incremental algorithm

Target: I can add a site to a Voronoi diagram one step at a time: bisector with the nearest site, travel to the next edge, turn, and close the cell. (+4 more)

By the end of this section

Key points

The incremental algorithm

  • Drawing every perpendicular bisector gives a messy diagram. Build the diagram one site at a time instead.
  • To add a site, draw the perpendicular bisector of the new site and its nearest site, as a dashed line. Travel along it until you reach an existing edge. That part is one edge of the new cell.
  • At the existing edge the new site is the same distance from three sites. Turn onto the bisector between the new site and the next site, and keep going until the cell closes.
  • If you reach the boundary of the region before the cell closes, go back to where you started and travel the other way.

Finding the new edges and vertices

  • The perpendicular bisector of two sites passes through their midpoint. Its gradient is the negative reciprocal of the gradient of the line joining the sites.
  • A new vertex is where two new bisectors meet. Write both as equations and solve them together on the calculator.
  • A new vertex is the same distance from the new site and two old sites. Check this with the distance formula.
  • On the boundary of the region, put the value of x or y of the boundary into the bisector equation.

What changes

  • The new cell takes over part of each cell it shares an edge with. Other cells do not change.
  • Old edges inside the new cell are rubbed out. An old vertex inside the new cell disappears.
  • An old vertex is inside the new cell when it is nearer the new site than the three old sites it was equidistant from.
  • Closing a site works the other way round. Its cell, edges and vertices are removed, and its neighbours take over the area. Find the bisectors of the neighbouring sites that now meet.

On the calculator

Solving two bisector equations for a vertex

  • Write each bisector as an equation in x and y.
  • Enter the two equations as a pair of simultaneous equations and solve.
  • The solution is the new vertex. Check it with the distance formula: it is the same distance from the three sites.

Screenshot and video to come

Explore: the perpendicular bisector

Drag the sites A and B. The working finds the perpendicular bisector line by line. Check that it matches the line on the grid.

Drag A or B.

  1. Move B until A and B have the same y-coordinate. What kind of line is the bisector now? Why can you not use the gradient formula?
  2. Multiply the gradient of AB by the gradient of the bisector. What do you get each time?
  3. Move A and B so that the midpoint stays where it is. What changes about the bisector, and what stays the same?
  4. Read the coordinates of a grid point on the shaded side. Is it nearer to A or to B? Check with the distance formula.

Explore: build a Voronoi diagram

Drag the sites, add one or take one away, and watch the cells change. Drag the orange point P to see which site is nearest to it.

Drag a site or the point P.

  1. Drag P across an edge. What happens to the nearest site? What is true about the two distances when P is on the edge?
  2. Tick the vertices and press one. How many sites are the same distance from it? What does the dashed circle show?
  3. Add a site close to the middle of the diagram. Which cells get smaller, and which cells do not change at all?
  4. Move two sites so that they are very close together. Where is the edge between them? Why is it so short or so long?

Explore: adding a site

Drag the new site E to any point, then press Next to add it one step at a time. In "Try it yourself", press the site each new edge is shared with before it is drawn.

Black: the diagram before. Orange: the new site and its edges. Teal: the cell the new edge is in. Dotted: the whole bisector.

Drag E, then press Next.

  1. The new edge between the new site and a neighbour is part of a perpendicular bisector. Why must it stop at an old edge?
  2. At the point where it stops, the new site is the same distance from how many sites? Why does the line turn there?
  3. Drag E close to a site, then far from every site. Which gives the larger new cell? Which cells change, and which do not?
  4. An old vertex is rubbed out. What must be true about its distance to the new site?

Worked examples

Problems like the ones in class. Pick one, try it, then open the working.
Adding a site to a diagram

The diagram shows the Voronoi diagram for the sites A, B, C and D. A new site E is added at (4, 4). Sketch the new diagram and find the vertices of the new cell.

1234567891234567xyABCDE
Working
  1. 1234567891234567xyABCDE
    Bisector with the nearest site

    EC bisector: \(x+y=9\)

    C is the nearest site to E. Draw the perpendicular bisector of EC as a dashed line. Every point on it is the same distance from E and C.

  2. 1234567891234567xyABCDE
    Travel to the next edge

    New edge from (3.5, 5.5) to (5.5, 3.5)

    Travel along the dashed line until it meets an existing edge, at each end. Those two points are new vertices.

  3. 1234567891234567xyABCDE
    Turn and keep going

    Bisectors EB and ED: \(2x-4y=-3\) and \(4x-2y=3\). From the calculator: (1.5, 1.5)

    At (1.5, 1.5) the new site is the same distance from B, D and itself. Turn onto the next bisector. Solve the two equations together to check the vertex.

  4. 1234567891234567xyABCDE
    Close the cell

    New cell: (1.5, 1.5), (3.5, 5.5), (5.5, 3.5)

    Join the vertices. Rub out the old edges inside the new cell. The old vertex (3.5, 3.5) goes.

Video walkthrough coming
The equation of a bisector

Find the equation of the perpendicular bisector of the sites A(2, 6) and D(4, 2).

Working
  1. Midpoint

    \(\left(\frac{2+4}{2},\frac{6+2}{2}\right)=(3, 4)\)

    The bisector passes through the midpoint of the two sites.

  2. Gradient

    \(\frac{2-6}{4-2}=-2\)

    This is the gradient of AD.

  3. Perpendicular gradient

    \(-\frac{1}{-2}=0.5\)

    The bisector is at right angles to the line joining the sites. Negative reciprocal.

  4. Equation

    \(y-4=0.5(x-3)\), so \(y=0.5x+2.5\)

    Use the midpoint and the new gradient.

Video walkthrough coming
A cell that reaches the boundary

The diagram shows the Voronoi diagram for the sites A, B, C and D in a rectangular region. A new site E is added at (7, 5). Find where the new edge between E and A meets the top of the region.

1234567891234567xyABCDE
Working
  1. 1234567891234567xyABCDE
    Bisector

    EA bisector: \(x-y=1\)

    Draw the perpendicular bisector of E and A.

  2. 1234567891234567xyABCDE
    Travel to the boundary

    The top of the region is y = 7. Put y = 7 into \(x-y=1\): x = 8

    The edge runs to the boundary and stops. On the boundary, one coordinate is known: put it into the bisector.

  3. 1234567891234567xyABCDE
    The other end

    New cell: (5.5, 4.5), (6, 3), (8, 7), (9, 0), (9, 7)

    Go back to where you started and travel the other way to find the rest of the cell.

Video walkthrough coming
Which old vertex disappears?

The Voronoi diagram for the sites A, B, C and D has a vertex at (3, 4). A new site E is added at (4, 4). Show that (3, 4) is not a vertex of the new diagram.

1234567891234567xyABCDE
Working
  1. The old vertex

    (3, 4) is equidistant from A, C, D

    An old vertex is the same distance from three sites.

  2. Distance to A

    \(\sqrt{(3-2)^2+(4-6)^2}=\sqrt{5}=2.24\)

    The same for the other two sites.

  3. Distance to E

    \(\sqrt{(3-4)^2+(4-4)^2}=\sqrt{1}=1.00\)

    E is nearer than any of the old sites.

  4. 1234567891234567xyABCDE
    Conclude

    1.00 < 2.24

    (3, 4) is inside the cell of E, so the old edges meeting there are rubbed out. It is not a vertex of the new diagram.

Video walkthrough coming
Taking a site away

The diagram shows the Voronoi diagram for four bus depots A(6, 5), B(5, 2), C(2, 3) and E(4, 3), where the units are kilometres. The depot at E closes. Find the vertex where the cells of A, B and C now meet, and say how many vertices the new diagram has inside the region.

1234567891012345678xyABCE
Working
  1. What goes

    The cell of E has vertices \((3, 1)\), \((3, 6)\), \((\frac{11}{2}, \frac{7}{2})\)

    When E closes, its cell, its three edges and its three vertices are removed. The area is shared out between A, B and C.

  2. The new vertex

    Bisectors of AB and BC: \(x+3y=16\) and \(3x-y=8\). From the calculator: (4, 4)

    With E gone, A, B and C are the three neighbours. Their cells meet where two of the bisectors cross.

  3. Check

    \(AV=BV=CV=\sqrt{5}=2.24\)

    The new vertex is the same distance from A, B and C.

  4. 1234567891012345678xyABC
    Redraw

    1 vertex inside the region

    Three edges meet at the new vertex and carry on to the boundary. Three vertices have become one.

Video walkthrough coming