13.05 Nearest neighbour interpolation
Nearest neighbour interpolation
Nearest neighbour interpolation allows us to estimate the value of a variable at any point using the nearest known data point or site. For instance, if you look up the air quality in your area it is estimated using the nearest air quality monitoring site.
To estimate a variable using Nearest neighbour interpolation at a particular point on a Voronoi diagram:
- Use the value of the site in the same cell as the point you are estimating for.
- If the point is on an edge, take the average of the values of the sites in the adjacent cells.
- If the point is on a vertex, take the average of the values of the sites of all the adjacent cells.
Worked example
example 1
The air quality index in northern Japan was measured at four different sites. The results are shown in the table and Voronoi diagram below.
| Location | Index | Rating |
|---|---|---|
| Asahikawa | $42$42 | Good |
| Kitami | $50$50 | Moderate |
| Kushiro | $30$30 | Good |
| Obihiro | $13$13 | Very good |
Akemi lives in Engaru which is shown in the above Voronoi diagram.
(a) Which location's air quality index should she use to estimate the air quality index where she lives?
(b) Estimate the air quality index of Engaru.
(c) Takeshi lives in Mikasa which is shown in the above Voronoi diagram. Estimate the air quality index of Mikasa.
(a) Engaru is in the same cell as Kitami, so she should use the air quality index for Kitami to estimate the air quality index for Engaru.
(b) The air quality of Kitami is $50$50 according to the table, so the estimate for Engaru is also $50$50.
(c) Mikasa is located on the edge between the cells containing the sites Obihiro and Asahikawa. So to estimate the air quality index of Mikasa, we should take the average of the air quality indexes of these adjacent sites:
| Average air quality index | $=$= | $\frac{42+13}{2}$42+132 |
| $=$= | $27.5$27.5 |
So the estimate for the air quality index for Mikasa is $27.5$27.5.
Largest empty circle
It is useful to be able to find the largest empty circle on a Voronoi diagram when we need to add a site that needs to be as far away from all the other sites as possible. This idea comes from the toxic waste dump problem, which aims to find the best location for the waste dump that is as far from the other towns as possible, since no one wants to live near a toxic waste dump!
The largest empty circle on any Voronoi diagram will have its centre at a vertex and the radius will be the length from that vertex to one of the adjacent sites.
To find the largest circle, we must measure the length from each vertex on the Voronoi diagram to a corresponding adjacent site. The longest length will be the radius of the largest circle, and that vertex will be the centre of the largest circle.
Worked example
example 2
A toxic waste dump is about to be built in Cyprus near the cities shown in the Voronoi diagram below.
(a) Find the largest empty circle for these sites.
(b) State the coordinates of the location where the toxic waste dump should be built.
(a) The largest circle may have its centre either at the vertex $V_1(-5,-1)$V1(−5,−1) or $V_2(1,1)$V2(1,1) :
Think: We can already see from the above image that the largest circle has its centre at $V_2(1,1)$V2(1,1), but it may not always be the case that we can see the larger circle so easily so we should still find the radius of each circle.
Do: So first let's find the radius from $V_1(-5,-1)$V1(−5,−1) to Limassol at $(-4,-4)$(−4,−4) :
| $r_1$r1 | $=$= | $\sqrt{(-5+4)^2+(-1+4)^2}$√(−5+4)2+(−1+4)2 |
| $=$= | $\sqrt{1+9}$√1+9 | |
| $=$= | $\sqrt{10}$√10 | |
| $=$= | $3.16...$3.16... |
So the radius of the circle with centre $V_1(-5,-1)$V1(−5,−1) is approximately $3.16$3.16 units.
Now lets find the radius from $V_2(1,1)$V2(1,1) to Limassol at $(-4,-4)$(−4,−4) :
| $r_1$r1 | $=$= | $\sqrt{(1+4)^2+(1+4)^2}$√(1+4)2+(1+4)2 |
| $=$= | $\sqrt{25+25}$√25+25 | |
| $=$= | $\sqrt{50}$√50 | |
| $=$= | $7.07...$7.07... |
So the radius of the circle with centre $V_2(1,1)$V2(1,1) is approximately $7.07$7.07 units, which is larger than the radius of the circle with centre $V_1(-5,-1)$V1(−5,−1).
So the largest empty circle for these sites is the circle with centre $V_2(1,1)$V2(1,1) and radius $7.07$7.07.
(b) The toxic waste dump should be built at the centre of the largest empty circle so that it is not too close to any of the cities. Therefore, it should be build at the location with coordinates $(1,1)$(1,1).