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

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

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 D, C, B, A.

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

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

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

   • Bisectors of EA and EB: \(x-2y=-1\) and \(3x-y=2\). From the calculator: (1, 1)
   • Bisectors of EB and ED: \(3x-y=2\) and \(x-y=-2\). From the calculator: (2, 4)
   • Bisectors of EC and ED: \(4x+2y=31\) and \(x-y=-2\). From the calculator: (4.5, 6.5)
   • Bisectors of EA and EC: \(x-2y=-1\) and \(4x+2y=31\). From the calculator: (6, 3.5)

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

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 (6.5, 2.5) is where A, B and C meet. Each is \(\sqrt{4.5}=2.12\) away.
   • Distance to E(6, 2): \(\sqrt{0.5}=0.707\)
   • 0.707 is less than 2.12, 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 C, A, B.
   • 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 (6, 1), and its cell reaches the edge of the region.

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

   • Midpoint of EA: \(\left(\frac{6+8}{2},\frac{1+3}{2}\right)=(7, 2)\)
   • Gradient of EA: \(\frac{3-1}{8-6}=1\). The bisector is perpendicular: gradient \(-\frac{1}{1}=-1\).
   • Through \((7, 2)\): \(y-2=-1(x-7)\), so \(y=-x+9\)

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 B meets the boundary at (3.5, 0). Check: it lies on \(2x=7\).
   • The new edge between E and A lies on \(y=-x+9\). Put \(y=0\): it meets the boundary at (9, 0), a corner of the region.
   • Travel along each new edge until you reach the boundary: the cell stops there.

A town has four supermarkets. Customers go to the nearest supermarket. The diagram shows the Voronoi diagram for the four existing supermarkets, with a new supermarket E that opens at (2, 5). 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 EC: \(2x+4y=19\) and \(x-y=-4\). From the calculator: (0.5, 4.5)
   • Bisectors of EC and ED: \(x-y=-4\) and \(x+y=8\). From the calculator: (2, 6)
   • Bisectors of EA and EB: \(2x+4y=19\) and \(2x-y=4\). From the calculator: (3.5, 3)
   • Bisectors of EB and ED: \(2x-y=4\) and \(x+y=8\). From the calculator: (4, 4)

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

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

A city has five post offices. The diagram shows the Voronoi diagram for the five existing post offices. A new post office F opens at (6, 3).

1. (a) Which existing post offices 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 A, E, B, C.

2. (b) Which existing post offices keep exactly the same cell?

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

A town has four libraries, A(5, 1), B(2, 7), C(1, 5) and E(2, 5), where the units are kilometres. The diagram shows the Voronoi diagram. The library at E closes.

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

   • Bisectors of AB and BC: \(2x-4y=-9\) and \(2x+4y=27\). From the calculator: \((\frac{9}{2}, \frac{9}{2})\)
   • Check: A, B and C are each \(3.54\) 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{3}{2})\), \((\frac{3}{2}, 6)\), \((\frac{15}{2}, 6)\)

Three Wi-Fi routers A, B and C are in a hall. Two more routers, D and then E, are installed one at a time, and each device connects to the nearest router. 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 m.

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 (6, 3.5), (6, 7), (7, 3), (9, 3), (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 (3, 2), (6, 5), (7, 2), (8, 3).

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

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