Opening Problem

The map below shows the location of four fire stations in a city:

• When a fire starts in the city, it is important that the nearest fire station is alerted.
  • Which fire station is closest to:
    • (6,3)
    • (4,6)
  • The Station Master at fire station D wants to know the region of the city that is closest to his station. What does this region look like?
  • How could we improve the map to make it easier to determine the closest fire station to any given location?
  • A new fire station is to built within the city grid. To maximise the efficiency of the fire stations, the new station should be built as far as possible from existing stations. Where should it be built?

Let’s consider the fire stations map a little closer, using the coloured map below to help us:

The colours show the regions which are closer to each station than any other station. Notice that each region contains exactly one station. For instance, (4,6) lies in the region containing B, so station B is the closest station to (4,6).

• Let’s learn some important language relating to Voronoi diagrams:
• Sites are important locations – so in the diagram above they are the locations of the fire stations.
• Cells are the regions surrounding the site that are closer to that site than any other site. We label them according to the site, as indicated in the diagram at the end of this list of definitions.
• Edges are the lines separating cells. Each point on an edge is equally close to the two sites whose cells are adjacent to that edge.
• Vertices are the points at which edges meet. Each vertex is equally close to the sites whose cells meet at that vertex.

Worked Example

Consider the below Voronoi diagram for the sites A, B, C and D:

• How many cells does this diagram contain?
• How many vertices does this diagram contain?
• Identify the site or sites closest to:
  • (2, -3)
  • (1,5)
  • (-1,-2)
• What can we say about points which lie on the green edge?

Exercise

Answers