Sites, cells, edges and vertices Problem set B Worked solutions

The diagram shows the Voronoi diagram for the sites \(A(9, 9)\), \(B(1, 3)\), \(C(5, 11)\).

1. (a) Write down the number of cells and the number of edges.

   • Each site has its own cell: 3 cells. There is one edge between each pair of cells: 3 edges.

2. (b) Write down the coordinates of the vertex.

   • The three edges meet at one point. Read its coordinates from the diagram: \((5, 6)\)
   • Check: \(AV=5\), \(BV=5\), \(CV=5\)

3. (c) What is the point where the edges meet called?

   • A point where edges meet is a vertex.

The sites \(A(5, 6)\), \(B(3, 11)\), \(C(10, 7)\), \(D(10, 11)\) are plotted on the grid. The sites A and D have an edge between two vertices.

1. (a) Find the equation of the edge between A and D, in the form \(px+qy=r\).

   • Midpoint: \((\frac{15}{2}, \frac{17}{2})\)
   • Gradient of the line through the two points: \(1\)
   • Perpendicular gradient: \(-1\)
   • \(y-\frac{17}{2}=-(x-\frac{15}{2})\)
   • \(x+y=16\)

2. (b) Draw the Voronoi diagram on a copy of the grid. Write down the coordinates of the two vertices.

   • Midpoints of neighbouring sites: AB \((4, \frac{17}{2})\), AC \((\frac{15}{2}, \frac{13}{2})\), AD \((\frac{15}{2}, \frac{17}{2})\), BD \((\frac{13}{2}, 11)\), CD \((10, 9)\)
   • Draw an edge through each midpoint at right angles to the line joining the two sites, and stop where edges meet.
   • The edges meet at two vertices: \((\frac{13}{2}, \frac{19}{2})\) and \((7, 9)\)
   • Check: each vertex is the same distance from three sites
   • The vertex \((\frac{13}{2}, \frac{19}{2})\) is \(\sqrt{\frac{29}{2}}=3.81\) from A, B, D
   • The vertex \((7, 9)\) is \(\sqrt{13}=3.61\) from A, C, D

The diagram shows the Voronoi diagram for the sites \(A(11, 1)\), \(B(2, 11)\), \(C(9, 11)\), \(D(2, 7)\). The point \(P(8, 6)\) is marked.

1. (a) Which site is nearest to P?

   • \((8, 6)\) lies in the cell of C, so C is the nearest site.

2. (b) Show that this is true by working out the distance from P to this site and to the next nearest site.

   • \(PC=\sqrt{26}=5.10\)
   • \(PA=\sqrt{34}=5.83\)
   • C is closer, as the diagram shows. The next nearest is A.

The sites \(A(6, 2)\), \(B(4, 5)\), \(C(1, 6)\), \(D(10, 3)\) are plotted on the grid.

1. (a) Do the cells of A and B share an edge? Use the midpoint of AB to explain.

   • Midpoint of AB: \((5, \frac{7}{2})\)
   • \(AM=\sqrt{\frac{13}{4}}=1.80\), \(BM=\sqrt{\frac{13}{4}}=1.80\), \(CM=\sqrt{\frac{89}{4}}=4.72\), \(DM=\sqrt{\frac{101}{4}}=5.02\)
   • The midpoint is 1.80 from A and from B, and nearer to them than to C or D. So A and B share an edge.

2. (b) Do the cells of C and D share an edge? Use the midpoint of CD to explain.

   • Midpoint of CD: \((\frac{11}{2}, \frac{9}{2})\)
   • \(AM=\sqrt{\frac{13}{2}}=2.55\), \(BM=\sqrt{\frac{5}{2}}=1.58\), \(CM=\sqrt{\frac{45}{2}}=4.74\), \(DM=\sqrt{\frac{45}{2}}=4.74\)
   • Site B is closer to the midpoint than C or D are, so B's cell comes between them. C and D do not share an edge.

Five bike-hire stands are at \(A(9, 10)\), \(B(1, 4)\), \(C(4, 1)\), \(D(3, 8)\), \(E(4, 5)\), where the units are hundreds of metres. The diagram shows three of the edges of the Voronoi diagram, dashed: the edges between E and A, B, C. The fourth edge of the cell containing E is the edge between E and D. A cyclist is at \(Q(4, 4)\).

1. (a) Find the equation of the line that forms the final edge of the cell containing E, in the form \(px+qy=r\).

   • Midpoint: \((\frac{7}{2}, \frac{13}{2})\)
   • Gradient of the line through the two points: \(-3\)
   • Perpendicular gradient: \(\frac{1}{3}\)
   • \(y-\frac{13}{2}=\frac{1}{3}(x-\frac{7}{2})\)
   • \(x-3y=-16\)

2. (b) Sketch the cell containing E and write down the coordinates of its vertices.

   • Draw the cell's four edges and mark where they meet: the vertices are \((11, 3)\), \((\frac{13}{2}, \frac{15}{2})\), \((2, 6)\), \((3, 3)\)
   • Join them to make the cell of E, then shade it.

3. (c) The cyclist at \(Q(4, 4)\) lies in the cell containing E. What does this tell you about the stand nearest to the cyclist?

   • \(QE=1\)
   • \(QB=3\)
   • Q is in the cell of E, so E is nearer to Q than any other stand.

Weather stations are at \(A(2, 2)\), \(B(10, 2)\), \(C(10, 8)\), where the units are kilometres. A fourth station D is built so that ABCD is a rectangle.

1. (a) Write down the coordinates of the fourth station D.

   • ABCD is a rectangle, so D has the x-coordinate of A and the y-coordinate of C: \((2, 8)\)

2. (b) Find the coordinates of the vertex where four edges meet, and show that it is the same distance from all four stations.

   • The vertex is the centre of the rectangle, the midpoint of AC: \((6, 5)\)
   • \(VA=5\), \(VB=5\), \(VC=5\), \(VD=5\)
   • Four equal distances, so four edges meet at the vertex.

3. (c) Explain why the cells of A and C do not share an edge.

   • A and C are opposite corners. Near the vertex the nearest sites are B and D, so the cells of B and D lie between the cells of A and C. The cells of A and C touch at the single point V only.

A market hall is a rectangle 12 units by 8 units on a plan, where one unit is 5 m. Four stalls are at \(A(2, 4)\), \(B(8, 5)\), \(C(2, 7)\) and \(E(3, 5)\). The cell of E is a triangle with vertices \((1.5, 5.5)\), \((5.5, 1.5)\) and \((5.5, 7.5)\).

1. (a) Find the area of the cell of E, in square units.

   • Base along \(x=5.5\): \(7.5-1.5=6\)
   • Height from \((1.5, 5.5)\) across to \(x=5.5\): \(4\)
   • \(\frac{1}{2}\times6\times4=12\) square units

2. (b) Find the area of the cell of E, in m².

   • One unit is 5 m, so one square unit is \(5\times5=25\) m²
   • \(12\times25=300\) m²

3. (c) Find the percentage of the hall that is nearer to E than to any other stall.

   • Hall: \(12\times8=96\) square units
   • \(\frac{12}{96}\times100=12.5\)
   • The scale does not change a percentage: \(12.5\%\)

Three libraries are at \(A(5, 8)\), \(B(9, 10)\), \(C(7, 4)\), where the units are kilometres. The edges of the Voronoi diagram between them meet at a vertex V.

1. (a) Find the equations of the edges between A and B and between A and C, in the form \(px+qy=r\).

   • Edge AB: \(2x+y=23\)
   • Edge AC: \(x-2y=-6\)

2. (b) Use your calculator to find the coordinates of the vertex V where these two edges meet.

   • From the calculator: solve \(2x+y=23\) and \(x-2y=-6\) together: \(x=8,\ y=7\)

3. (c) Show that V is the same distance from A, B and C.

   • \(VA=\sqrt{10}=3.16\)
   • \(VB=\sqrt{10}=3.16\)
   • \(VC=\sqrt{10}=3.16\)
   • The distances are equal, so V is on all three edges.

Four water pumps are at \(A(11, 6)\), \(B(4, 9)\), \(C(4, 3)\), \(D(7, 6)\), where the units are hundreds of metres. D is inside the triangle formed by A, B and C. Every point is assigned to its nearest pump.

1. (a) Find the coordinates of the vertices of the cell containing D.

   • Edges of D's cell: D and A: \(x=9\), D and B: \(x-y=-2\), D and C: \(x+y=10\)
   • From the calculator, solve each pair of equations: the vertices are \((9, 1)\), \((9, 11)\), \((4, 6)\)

2. (b) How many edges does D's cell have? What does this tell you about where D is?

   • The cell of D has 3 edges, one with each of A, B and C. D lies inside triangle ABC, so no edge of its cell goes off to infinity: its cell is a triangle.