Menu
Sign up Sign in

AI SL · 12.8

Voronoi Diagrams

0 of 19 skills done

0
12.8.5

Nearest neighbour interpolation

12.8.5

Nearest neighbour interpolation

Target: I can find the cell that contains a point on a Voronoi diagram and read the estimate for that point from its site. (+3 more)

By the end of this section

Key points

Nearest neighbour interpolation

  • The value of a quantity (rainfall, temperature, a price) is known at the sites only. The sites might be weather stations or sensors.
  • To estimate the value at any other point, use the value at the nearest site. That is the site whose cell contains the point.
  • Every point in one cell gets the same estimate. The estimate changes only when you cross an edge.
  • Write it as a sentence: "The point is in the cell of site G, so the estimate is 20."

When the picture is not enough

  • Close to an edge you cannot tell the cell by eye. Find the distance from the point to each site nearby and take the smallest: \(d=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\).
  • To compare two distances you can compare \(d^2\). There is no square root to find.
  • With no diagram, the same method works: the nearest site is the one with the smallest distance.
  • A point on an edge is the same distance from two sites, so the method gives no single answer. Questions avoid these points.

How good is the estimate?

  • The estimate is a model. The actual value is usually different.
  • Percentage error \(=\dfrac{|\text{estimate}-\text{actual}|}{|\text{actual}|}\times 100\%\). Divide by the actual value, not the estimate.
  • The estimate is poor far from every site. A new site near the point makes it better.
  • A new site changes the cells near it. A point inside the new cell takes the new site's value.

Explore: estimating a value

Drag the point P. The estimate at P is the value at its nearest site, the site whose cell P is in.

Distance from P to each site (d² is the distance squared)
SiteValued²d

Drag P, or use the arrow keys.

  1. Move P inside one cell. What happens to the estimate? What happens when P crosses an edge?
  2. Put P as close to an edge as you can. What do the distances to the two nearest sites show?
  3. Where on the diagram would you trust the estimate least? Why?
  4. Where would you put one more site to make the estimate better at the corner farthest from every site? Sketch the new cells on paper.

Explore: build a Voronoi diagram

Drag the sites, add one or take one away, and watch the cells change. Drag the orange point P to see which site is nearest to it.

Drag a site or the point P.

  1. Drag P across an edge. What happens to the nearest site? What is true about the two distances when P is on the edge?
  2. Tick the vertices and press one. How many sites are the same distance from it? What does the dashed circle show?
  3. Add a site close to the middle of the diagram. Which cells get smaller, and which cells do not change at all?
  4. Move two sites so that they are very close together. Where is the edge between them? Why is it so short or so long?

Worked examples

Problems like the ones in class. Pick one, try it, then open the working.
Reading the value from a cell

A nature reserve has seven bird hides. The diagram shows the Voronoi diagram for the hides, with the number of birds counted at each hide on Saturday. Use nearest neighbour interpolation to estimate the number of birds a visitor would see at the point (1, 5).

1234567891234567xyA 7B 12C 18D 5E 9F 15G 21
Working
  1. Find the cell

    (1, 5) is in the cell of site E

    Find the point on the grid. Look for the cell it is in. Each cell belongs to one site.

  2. Read the value

    Site E has the value 9

    The label beside the site gives the count there.

  3. State the estimate

    Estimate = 9 birds

    Every point in this cell has the same estimate.

Video walkthrough coming
A point close to an edge

The diagram shows a Voronoi diagram for seven river gauges. Each site shows the pollution level in mg per litre. Estimate the pollution level at the point (5, 4), which is close to an edge.

1234567891234567xyA 14B 9C 22D 17E 6F 11G 25
Working
  1. The picture is unclear

    (5, 4) is near the edge between C and A

    You cannot tell the cell by eye. Compare distances.

  2. Distance to C

    \(d^2=(5-4)^2+(4-5)^2=2\)

    Leave it as d². You can compare squares.

  3. Distance to A

    \(d^2=(5-5)^2+(4-2)^2=4\)

    2 is less than 4, so C is nearer.

  4. State the estimate

    Estimate = 22 mg per litre

    The point is in the cell of C.

Video walkthrough coming
How good is the estimate?

The diagram shows a Voronoi diagram for seven estate agents. Each site shows the average price of a flat per m², in euros, for its area. A flat at the point (8, 3) sells for € 3 800 per m². Use nearest neighbour interpolation to estimate its price per m², and find the percentage error in the estimate.

1234567891234567xyA 2 900B 3 400C 4 200D 3 700E 5 100F 4 600G 3 100
Working
  1. Find the cell

    (8, 3) is in the cell of site D

    The nearest site gives the estimate.

  2. The estimate

    Estimate = € 3 700 per m²

    Read the price at the site.

  3. Percentage error

    \(\dfrac{|3700-3800|}{3800}\times 100=2.63\)

    Divide by the actual value, 3 800, not by the estimate.

  4. State

    Percentage error = 2.63%

    The estimate is too low by about this percentage.

Video walkthrough coming