Voronoi diagrams in the real world Problem set A Worked solutions

Three clinics are at \(A(2, 3)\), \(B(10, 2)\), \(C(6, 10)\), where the units are kilometres. A patient lives at \(P(5, 5)\). The patient goes to the nearest clinic.

1. (a) Work out the distance from P to each site.

   • \(PA=\sqrt{13}=3.61\)
   • \(PB=\sqrt{34}=5.83\)
   • \(PC=\sqrt{26}=5.10\)

2. (b) Which site's cell is P in?

   • The smallest distance is to A, so P is in the cell of A.

A Voronoi diagram shows the areas served by fire stations X and Y. A point Z on the edge between the two cells is 7 km from station X. A point W lies in the cell of X.

1. (a) How far is Z from station Y?

   • Z is on the edge, so it is the same distance from X and from Y: 7 km.

2. (b) What can you say about the distance from W to station X compared with the distance from W to station Y?

   • W is in the cell of X, so X is the nearest site to W.

A town council has a map of its schools, bus routes and rivers. Which of these can a Voronoi diagram answer? (i) The area closest to each school. (ii) The quickest route by bus between two schools. (iii) Which school is nearest to a given house, in a straight line. (iv) The number of pupils at each school.

• Voronoi diagrams use straight-line distance to the nearest site. (i) and (iii) are about the nearest site. (ii) depends on routes and (iv) is not about distance.

Four cafés are at \(A(10, 11)\), \(B(10, 2)\), \(C(1, 3)\), \(D(4, 8)\), where the units are hundreds of metres. The Voronoi diagram is drawn, with three flats P, Q and R marked. A new café opens at \(N(2, 2)\).

1. (a) From the diagram, write down the nearest site to each of the flats P, Q and R.

   • Read which cell each point is in: P in the cell of C, Q in the cell of B, R in the cell of D

2. (b) A new café opens at N. Work out which of the flats is nearer to N than to its old nearest site.

   • P: old nearest \(CP=\sqrt{20}=4.47\), new \(NP=\sqrt{10}=3.16\)
   • Q: old nearest \(BQ=4\), new \(NQ=\sqrt{80}=8.94\)
   • R: old nearest \(DR=\sqrt{2}=1.41\), new \(NR=\sqrt{34}=5.83\)
   • Only flat P is closer to the new café.

A town has several dental surgeries.

1. (a) Say what the sites are, what a cell shows, and one question the diagram answers.

   • Sites: the surgeries. Cell: the addresses nearest to one surgery. Question: which surgery is nearest to this address?

2. (b) Give one thing the model leaves out.

   • Straight-line distance is used, not the distance by road. A surgery with a long waiting list is treated like any other.

Two phone masts are at \(X(2, 3)\) and \(Y(10, 3)\), where the units are kilometres. A house is at \(H(6, 7)\). A hill lies between H and mast X.

1. (a) Show that H is on the edge between the cells of X and Y.

   • \(XH=\sqrt{32}=5.66\)
   • \(YH=\sqrt{32}=5.66\)
   • The distances are equal, so H is on the edge between the cells of X and Y.

2. (b) Explain why the Voronoi model may not give the best mast for the house, and suggest one way to improve the model.

   • The Voronoi model assumes the nearest mast is best. A hill blocks the signal, so the house may get a better signal from Y even though the distances are equal. Use a measure that includes the hill, such as signal strength instead of distance.