Select Page

SL AI – Voronoi problem solving

Nearest Neighbour Interpolation

The Voronoi diagram below is a diagram to show 5 different areas of a ski resort and the current ski depth.

• In the interpolation we estimate  that if you are in a cell you can assume that you will have the same value as the site. For example if you are at point (-1,-2) you are closest to D and you can expect the snow depth to be 180 cm.
• If you are at a vertex point then you do a mean average of the sites closest to that vertex point. For example of you are at (2,-2) you can expect to have 183.33 cm of snow depth. This is (230+140+180)/3=183.3

The Voronoi diagram below is a diagram to show 5 different areas of a ski resort and the current ski depth.

1. If you are at (-4,2) find an estimate of the snow depth.

2. If you are at (2,3) find an estimate of the snow depth.

3. If you are at (4,2) find an estimate of the snow depth.

4. If you are at (0,-1) find an estimate of the snow depth.

1. 160 cm,   closest to A

2. 230 cm,   closest to E.

3. 193.3 cm,   closest to B,C, and E.

4. 205 cm,   closest to D and E.

Toxic Waste Dump Problem

The Toxic Waste Dump Problem is the idea of finding a place that maximises the distance from the nearest town.

It is easy for 3 sites as there will only be one vertex. It becomes more challenging with multiple vertices.

The distance from the vertex chosen to the closest town (the radius) is called the largest empty circle.

Find the centre and radius of the largest empty circle for the Voronoi diagram shown below.

The centre is at (1,1) and the radius is 5.

You can check the distance from the centre to either A, B, or C and the answer is 5.

Find the centre and radius of the largest empty circle for the Voronoi diagram shown below.

The vertices have been given, but they are approximate values.

We need to investigate all three vertices and choose the one that creates the largest empty circle.

V1 is closest to A, B, E and has radius of approximately 5.

V2 is closest to B, C, D and has radius of approximately 4.

V3 is closest to A, B, C and has radius of approximately 4.

We choose V1 (-3,6) with a radius of approximately 5 units.