Voronoi diagrams: exam review Exam review: second paper Worked solutions

Three libraries are at \(A(3, 9), B(1, 2), C(10, 6)\), where the units are kilometres. Each home uses its nearest library, and the Voronoi diagram shows the area served by each library. A home is at \(H(6, 4)\). [6]

1. (a) Find the distance from H to each library. [3]

   • M1 for using the distance formula
   • A1 for any two distances correct
   • A1 for all three: A: \(\sqrt{34}=5.83\), B: \(\sqrt{29}=5.39\), C: \(\sqrt{20}=4.47\)

2. (b) Write down the library that is nearest to H. [1]

   • A1 for C (the smallest distance, 4.47)

3. (c) A second home G is the same distance from library B and from library C, and these are its two nearest libraries. Say where G is on the Voronoi diagram. [1]

   • A1 for on the edge (boundary) between the cells of B and C

4. (d) Give one thing that the Voronoi model leaves out. [1]

   • R1 for one valid thing left out, for example bus routes and walking routes (the model uses only the straight-line distance)

A Voronoi diagram has the sites \(P(-3, -1)\) and \(Q(5, 5)\). The line segment RS has equation \(5x+4y=22\) and midpoint \((2, 3)\). [6]

1. (a) Find the midpoint of PQ. [1]

   • A1 for \((1, 2)\)

2. (b) Find the equation of the perpendicular bisector of PQ, in the form \(y=mx+c\). [3]

   • M1 for the gradient of PQ: \(\frac{3}{4}\)
   • M1 for the perpendicular gradient: \(-\frac{4}{3}\), and using the midpoint \((1, 2)\)
   • A1 for \(y=-\frac{4}{3}x+\frac{10}{3}\)

3. (c) Find the equation of the perpendicular bisector of RS, in the form \(px+qy=r\), where p, q and r are integers. [2]

   • M1 for the gradient of RS: \(-\frac{5}{4}\), so the perpendicular gradient is \(\frac{4}{5}\), through \((2, 3)\)
   • A1 for \(4x-5y=-7\)

A lake has three fishing huts, A, B and C, where the units are hundreds of metres. The diagram shows the Voronoi diagram for the three sites \(A(3, 1), B(9, 5), C(5, 8)\). The point P\((8, 3)\) is marked. [6]

1. (a) Write down the number of edges in the diagram, and the name of the point where they meet. [2]

   • A1 for 3 edges
   • A1 for vertex

2. (b) Find the equation of the edge between A and B, in the form \(px+qy=r\). [3]

   • M1 for the midpoint of AB: \((6, 3)\)
   • M1 for the gradient of AB: \(\frac{2}{3}\), so the edge has gradient \(-\frac{3}{2}\)
   • A1 for \(3x+2y=24\)

3. (c) Write down the site that is nearest to P, and give a reason. [1]

   • A1 for B, because P is inside the cell of B (or: B has the smallest distance, 2.24)

A city measures air pollution with monitors in a park. The diagram shows the Voronoi diagram for the six monitors A to F, with the pollution level at each site. One unit on each axis is 100 m. The points \(X(2, 2)\) and \(Y(7, 3)\) are marked. [7]

1. (a) Use nearest neighbour interpolation to estimate the pollution level at X. [1]

   • A1 for 14 units (X is in the cell of A)

2. (b) The pollution level at X was later measured as 17 units. Find the percentage error in the estimate. [2]

   • M1 for \(\frac{|14-17|}{17}\times 100\)
   • A1 for 17.6%

3. (c) The point Y is close to an edge. Find the distance from Y to F and to C, and hence estimate the pollution level at Y. [3]

   • M1 for using the distance formula from Y to both sites
   • A1 for \(\sqrt{4}=2.00\) and \(\sqrt{5}=2.24\)
   • A1 for 26 units (F is nearer)

4. (d) Explain why the estimate at Y is less reliable than the estimate at X. [1]

   • R1 for saying Y is almost equidistant from two sites (close to an edge), so the other site's value could be as good, whereas X is well inside one cell

Two radio masts are at \(A(9, 2)\) and \(B\), where the units are kilometres. The perpendicular bisector of AB has equation \(3x-2y=10\). [8]

1. (a) Find the equation of the line AB, in the form \(y=mx+c\). [2]

   • M1 for the gradient of AB, perpendicular to the bisector: the bisector has gradient \(\frac{3}{2}\), so AB has gradient \(-\frac{2}{3}\), and AB passes through A
   • A1 for \(y=-\frac{2}{3}x+8\)

2. (b) Use your calculator to find the coordinates of the midpoint M of AB. [2]

   • M1 for solving the equation of AB and the equation of the bisector together (From the calculator)
   • A1 for \((6, 4)\)

3. (c) Hence find the coordinates of B. [1]

   • A1 for \((3, 6)\) (M is the midpoint of AB, so B = 2M - A)

4. (d) A straight railway has equation \(y=x\). A station on the railway is the same distance from the two masts. Find the coordinates of the station. [2]

   • M1 for solving the equation of the bisector and the equation of the road together (From the calculator)
   • A1 for \((10, 10)\)

5. (e) Find the distance from the station to A, in kilometres, to 3 significant figures. [1]

   • A1 for \(\sqrt{65}=8.06\) km (equal to the distance to B)

Four bus stops are at \(A(5, 2), B(7, 4), C(4, 4), D(3, 5)\), where one unit is 100 m. The diagram shows the Voronoi diagram for the four stops. A new stop E is built at \(E(5, 3)\), and the Voronoi diagram is redrawn. [10]

1. (a) Find the equation of the perpendicular bisector of E and C, in the form \(y=mx+c\). [3]

   • M1 for the midpoint of E and C: \((\frac{9}{2}, \frac{7}{2})\)
   • M1 for the gradient of EC: \(-1\), so the bisector has gradient \(1\)
   • A1 for \(y=x-1\)

2. (b) The perpendicular bisector of E and B has equation \(4x+2y=31\). Use your calculator to find the coordinates of the vertex where this bisector meets the bisector from part (a). [2]

   • M1 for solving \(y=x-1\) and \(4x+2y=31\) together (From the calculator)
   • A1 for \((\frac{11}{2}, \frac{9}{2})\)

3. (c) The old diagram has a vertex at \(V(\frac{11}{2}, \frac{7}{2})\). Show that V is not a vertex of the new diagram. [3]

   • M1 for the distance from V to a site it was equidistant from: \(VA=\sqrt{2.5}=1.58\) (the same for B, C)
   • M1 for the distance from V to E: \(VE=\sqrt{0.5}=0.707\)
   • R1 for VE is smaller, so V is inside the cell of E and is not a vertex of the new diagram

4. (d) Write down the stops whose cells share an edge with E, and the number of edges of the cell of E. [2]

   • A1 for A, B, C
   • A1 for 3 edges (one with each of A, B, C)

A national park has five visitor centres at \(A(5, 5), B(8, 5), C(8, 1), D(7, 3), E(3, 3)\), where one unit is 1 km. The diagram shows their Voronoi diagram in a rectangular region \(0\le x\le 9\), \(0\le y\le 7\). The vertices inside the region are P\((5, \frac{3}{4})\), Q\((5, 3)\), R\((\frac{13}{2}, \frac{9}{2})\). A waste site is to be placed anywhere in the region, including its boundary, as far as possible from every centre. [10]

1. (a) Find the distance from each of P, Q and R to its nearest centre. Give your answers to 3 significant figures. [3]

   • M1 for using the distance formula from a vertex to a site next to it
   • A1 for two distances correct
   • A1 for all three: P\((5, \frac{3}{4})\): nearest C\((8, 1)\), \(d=\sqrt{9.0625}=3.01\); Q\((5, 3)\): nearest A\((5, 5)\), \(d=\sqrt{4}=2.00\); R\((\frac{13}{2}, \frac{9}{2})\): nearest A\((5, 5)\), \(d=\sqrt{2.5}=1.58\)

2. (b) Write down which of P, Q and R is farthest from its nearest centre. [1]

   • A1 for P, the greatest (3.01)

3. (c) Find the distance from each corner of the region to its nearest centre, to 3 significant figures. [3]

   • M1 for the distance from a corner to its nearest site
   • A1 for two correct
   • A1 for all four: (0, 0): nearest E, \(\sqrt{18}=4.24\); (9, 0): nearest C, \(\sqrt{2}=1.41\); (9, 7): nearest B, \(\sqrt{5}=2.24\); (0, 7): nearest E, \(\sqrt{25}=5.00\)

4. (d) Hence write down where the waste site should be placed, and its distance from the nearest centre. [2]

   • A1 for the corner \((0, 7)\) with distance 5.00
   • R1 for the corner is farther than every vertex (the greatest vertex distance is 3.01), because the region has a boundary

5. (e) A rule says the waste site must be at least 5.5 units from every centre. Can the rule be met? Give a reason. [1]

   • A1 for no: the best place is 5.00 units from the nearest centre, which is less than 5.5

Three farms are at \(A(9, 3), B(11, 9), C(5, 11)\), where one unit is 20 km. A waste site is to be placed as far as possible from all three farms. Assume that it goes at the vertex V of their Voronoi diagram. [10]

1. (a) Find the equation of the perpendicular bisector of A and B, in the form \(y=mx+c\). [3]

   • M1 for the midpoint of AB: \((10, 6)\)
   • M1 for the gradient of AB: \(3\), so the bisector has gradient \(-\frac{1}{3}\)
   • A1 for \(y=-\frac{1}{3}x+\frac{28}{3}\)

2. (b) Find the equation of the perpendicular bisector of B and C, in the form \(y=mx+c\). [2]

   • M1 for the midpoint of BC: \((8, 10)\) and the perpendicular gradient \(3\)
   • A1 for \(y=3x-14\)

3. (c) Use your calculator to find the coordinates of V. [2]

   • M1 for solving \(y=-\frac{1}{3}x+\frac{28}{3}\) and \(y=3x-14\) together (From the calculator)
   • A1 for \((7, 7)\)

4. (d) Show that V is the same distance from A, from B and from C. [2]

   • M1 for the distance formula from V to at least two sites: \(VA^2=20\), \(VB^2=20\), \(VC^2=20\)
   • R1 for all three equal (\(\sqrt{20}\)), so V is the same distance from A, B and C

5. (e) Find the distance from the waste site to the nearest farm, in kilometres, to 3 significant figures. [1]

   • A1 for \(\sqrt{20}\times 20=89.4\) km

A lake is a rectangle 10 km by 8 km. Four buoys are at \(A(5, 5), B(7, 4), C(5, 2)\) and \(E(6, 4)\), where one unit is 1 km. The diagram shows the Voronoi diagram for the four buoys. The cell of E is a triangle with vertices \(P(\frac{13}{2}, \frac{11}{2})\), \(Q(\frac{13}{2}, \frac{5}{2})\) and \(R(\frac{9}{2}, \frac{7}{2})\). [10]

1. (a) Find the area of the cell of E. [2]

   • M1 for the base and the height of the triangle (or the coordinates in the area formula)
   • A1 for \(3.00\) km\(^2\)

2. (b) Find the percentage of the lake that is nearer to E than to any other buoy, to 3 significant figures. [2]

   • M1 for \(3\div(10\times8)\times100\)
   • A1 for 3.75%

3. (c) Buoy E is now removed. Find the equation of the perpendicular bisector of A and B, in the form \(y=mx+c\). [3]

   • M1 for the midpoint of A and B: \((6, \frac{9}{2})\)
   • M1 for the gradient of AB: \(-\frac{1}{2}\), so the bisector has gradient \(2\)
   • A1 for \(y=2x-\frac{15}{2}\)

4. (d) The perpendicular bisector of B and C is \(y=-x+9\). Use your calculator to find the coordinates of the new vertex where the cells of A, B and C meet. [2]

   • M1 for solving the two bisectors together (From the calculator)
   • A1 for \((\frac{11}{2}, \frac{7}{2})\)

5. (e) Write down the number of vertices of the old diagram that are removed. [1]

   • A1 for 3 (the three vertices of the cell of E)