Voronoi diagrams in the real world Problem set B Worked solutions

Three libraries are at \(D(9, 9)\), \(E(1, 3)\), \(F(5, 1)\), where the units are kilometres. A student lives at \(P(4, 6)\). The student goes to the nearest library.

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

   • \(PD=\sqrt{34}=5.83\)
   • \(PE=\sqrt{18}=4.24\)
   • \(PF=\sqrt{26}=5.10\)

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

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

A Voronoi diagram shows the areas covered by weather stations X and Y. A point Z on the edge between the two cells is 9 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: 9 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 city planner has a map of the city's supermarkets and its roads. Which of these can a Voronoi diagram answer? (i) The area in which each supermarket is the nearest one. (ii) The shortest driving route to a supermarket. (iii) Which supermarket is nearest to a given address, in a straight line. (iv) The average shopping bill at each supermarket.

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

Four bike-hire stands are at \(A(5, 2)\), \(B(1, 11)\), \(C(11, 3)\), \(D(1, 6)\), where the units are hundreds of metres. The Voronoi diagram is drawn, with three offices P, Q and R marked. A new stand opens at \(N(10, 2)\).

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

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

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

   • P: old nearest \(CP=\sqrt{5}=2.24\), new \(NP=1\)
   • Q: old nearest \(AQ=\sqrt{5}=2.24\), new \(NQ=\sqrt{20}=4.47\)
   • R: old nearest \(DR=\sqrt{5}=2.24\), new \(NR=\sqrt{74}=8.60\)
   • Only office P is closer to the new stand.

A district has several primary schools.

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

   • Sites: the schools. Cell: the homes nearest to one school. Question: which school is nearest to this home?

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

   • Straight-line distance is used, not the walking route. The size of each school is ignored.

Two radio transmitters are at \(X(2, 9)\) and \(Y(10, 5)\), where the units are kilometres. A farm is at \(H(7, 9)\). A mountain lies between H and transmitter X.

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

   • \(XH=5\)
   • \(YH=5\)
   • 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 transmitter for the farm, and suggest one way to improve the model.

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