Adding a site: the incremental algorithm Problem set B Worked solutions

The diagram shows the Voronoi diagram for the sites A, B, C and D. A new site E is added at (3, 3).

1. (a) Write down the sites that share an edge with E in the new diagram.

   • The new cell is the region nearer to E than to any other site.
   • Its edges lie on the bisectors of E and each of C, B, A, D.

2. (b) Find the equation of the perpendicular bisector of E and C.

   • Midpoint of EC: \(\left(\frac{3+2}{2},\frac{3+4}{2}\right)=(2.5, 3.5)\)
   • Gradient of EC: \(\frac{4-3}{2-3}=-1\). The bisector is perpendicular: gradient \(-\frac{1}{-1}=1\).
   • Through \((2.5, 3.5)\): \(y-3.5=1(x-2.5)\), so \(y=x+1\)

3. (c) Find the coordinates of the vertices of the new cell around E.

   • Bisectors of EB and EC: \(2x+4y=13\) and \(x-y=-1\). From the calculator: (1.5, 2.5)
   • Bisectors of EA and EC: \(x-3y=-11\) and \(x-y=-1\). From the calculator: (4, 5)
   • Bisectors of EB and ED: \(2x+4y=13\) and \(2x-y=8\). From the calculator: (4.5, 1)
   • Bisectors of EA and ED: \(x-3y=-11\) and \(2x-y=8\). From the calculator: (7, 6)

The diagram shows the Voronoi diagram for the sites A, B, C and D. A new site E is added at (5, 4).

1. (a) One vertex of the old diagram is not a vertex of the new diagram. Write down its coordinates and show that it is nearer to E than to the sites it was equidistant from.

   • The vertex (5, 3.5) is where A, B and C meet. Each is \(\sqrt{6.25}=2.50\) away.
   • Distance to E(5, 4): \(\sqrt{0.25}=0.500\)
   • 0.500 is less than 2.50, so the vertex is inside the new cell and is removed.

2. (b) How many edges does the new cell around E have?

   • Count the edges of the new cell: one for each of B, C, A.
   • It has 3 edges.

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 (5, 4), and its cell reaches the edge of the region.

1. (a) Find the equation of the perpendicular bisector of E and C.

   • Midpoint of EC: \(\left(\frac{5+5}{2},\frac{4+2}{2}\right)=(5, 3)\)
   • EC is vertical, so the bisector is horizontal.
   • Equation: \(y=3\)

2. (b) Write down the coordinates of the points where the edges of the new cell meet the boundary of the region.

   • The new edge between E and C meets the boundary at (9, 3). Check: it lies on \(y=3\).
   • The new edge between E and D lies on \(x+y=7\). Put \(x=0\): it meets the boundary at (0, 7), a corner of the region.
   • Travel along each new edge until you reach the boundary: the cell stops there.

A beach has four lifeguard towers. A swimmer in trouble is helped from the nearest tower. The diagram shows the Voronoi diagram for the four existing lifeguard towers, with a new tower E that opens at (2, 3). One unit on each axis is 1 km.

1. (a) Find the coordinates of the vertices of the new cell around E.

   • Bisectors of EA and EB: \(x+y=4\) and \(2x-4y=-13\). From the calculator: (0.5, 3.5)
   • Bisectors of EA and EC: \(x+y=4\) and \(x-y=0\). From the calculator: (2, 2)
   • Bisectors of EB and ED: \(2x-4y=-13\) and \(2x+y=12\). From the calculator: (3.5, 5)
   • Bisectors of EC and ED: \(x-y=0\) and \(2x+y=12\). From the calculator: (4, 4)

2. (b) Find the greatest distance from E to a vertex of its cell.

   • Distance from E(2, 3) to (0.5, 3.5): \(\sqrt{2.5}=1.58\)
   • Distance from E(2, 3) to (2, 2): \(\sqrt{1}=1.00\)
   • Distance from E(2, 3) to (3.5, 5): \(\sqrt{6.25}=2.50\)
   • Distance from E(2, 3) to (4, 4): \(\sqrt{5}=2.24\)
   • The greatest is 2.50 km.

A region has five fire stations. The diagram shows the Voronoi diagram for the five existing fire stations. A new fire station F opens at (7, 5).

1. (a) Which existing fire stations lose part of their cell when F is added?

   • A cell loses ground only if it shares an edge with the new cell.
   • The new cell has edges with D, E, C, B.

2. (b) Which existing fire stations keep exactly the same cell?

   • A: no edge with the new cell, so the cell does not change.

A city has four ambulance stations, A(3, 4), B(5, 2), C(1, 2) and E(3, 3), where the units are kilometres. The diagram shows the Voronoi diagram. The station at E is shut for repairs.

1. (a) Find the coordinates of the vertex where the cells of the three remaining sites meet.

   • Bisectors of AB and BC: \(x-y=1\) and \(x=3\). From the calculator: \((3, 2)\)
   • Check: A, B and C are each \(2.00\) from the vertex

2. (b) Write down the coordinates of the vertices that are removed from the diagram.

   • The cell of E is a triangle, and all three of its vertices go.
   • The vertices removed are \((\frac{3}{2}, \frac{7}{2})\), \((3, \frac{1}{2})\), \((\frac{9}{2}, \frac{7}{2})\)

Three cafés A, B and C are on a university campus. Two more cafés, D and then E, open one at a time, and each student goes to the nearest café. The diagram shows the Voronoi diagram for A, B and C, and the positions of D and E. One unit on each axis is 1 km.

1. (a) Find the coordinates of the vertices of the cell around D after D is added. Include any corner of the region in the cell, and any point where its edges meet the boundary.

   • Add D to the diagram for A, B and C.
   • The cell of D has vertices (4, 4.5), (4, 7), (5, 4), (9, 4), (9, 7).

2. (b) Find the coordinates of the vertices of the cell around E after E is added to the diagram for A, B, C and D.

   • Now add E to the new diagram of four sites.
   • The cell of E has vertices (1, 3), (4, 6), (5, 3), (6, 4).

A national park has four ranger stations. The diagram shows the Voronoi diagram for the four existing ranger stations. A new one, E, opens at (4, 3). Two of the existing ranger stations that shared an edge before no longer share an edge. Which two, and why?

• Before, B and D shared the edge from (4, 3.5) to (5, 3).
• Both ends of that edge are nearer to E than to B and D:
• (4, 3.5): to E \(\sqrt{0.25}\), to B and to D \(\sqrt{6.25}\)
• (5, 3): to E \(\sqrt{1}\), to B and to D \(\sqrt{5}\)
• So the whole edge lies in the new cell and is removed.