3.5.1 Voronoi Diagrams

What are Voronoi Diagrams?

• A Voronoi diagram shows the region containing the set of all points which are closer to one given site than to any other site on the diagram
  • A site is located at the coordinates of a specific place of interest on a Voronoi diagram
• It will be partitioned into a number of regions
  • These regions are often called Voronoi cells and will be polygons
    • There will be the same number of regions as sites on the diagram
  • For example, if a city contains five parks a Voronoi diagram could be drawn for that city dividing it into five regions based on their closest park
• The edges of each region will be the perpendicular bisector of two of the sites
  • The edges may also be called boundaries
• The vertices of each region are the intersections of three of these perpendicular bisectors
  • The perpendicular bisectors of three individual points will always intersect at the point that is equidistant from the three points

How are Voronoi diagrams drawn for three sites?

• You will not be expected to draw a Voronoi diagram from scratch, however you should understand how one is constructed
  • First, the perpendicular bisector of the line segment joining each pair of sites will be constructed
    • These should be constructed using dashed lines as only a part of each line will be needed for the final diagram
  • The points of intersection of these perpendicular bisectors will create the vertices
  • Each perpendicular bisector should stop when it meets another perpendicular bisector
    • Remove the part of the perpendicular bisector that is not in the region of the two sites
    • No perpendicular bisector should cross over another
    • This will form the regions, or cells

How are Voronoi diagrams drawn for more than three sites?

• It is challenging to draw a Voronoi diagram from scratch if it has more than three sites
• In this case it is easiest to draw the Voronoi diagram for three sites first and then add the next sites one by one following these steps

• • STEP 1: The fourth site will be in one of the cells containing an existing site

• • • Draw the perpendicular bisector of the line segment between these two sites

• • STEP 2: Stop this new line at the point where it meets an existing boundary in the Voronoi diagram
  • STEP 3: There will now be an existing edge in the region of the new site

• • • This should be shortened to meet the new boundary

• • STEP 4: The fourth site will now be in the same cell as a different existing site

• • • Draw the perpendicular bisector of the line segment between these two sites
    • This is the step you will most likely carry out in an exam
• You may be asked to find the equation of a missing edge
  • This will mean finding the equation of the perpendicular bisector between the two sites that are both within one region
• You may be asked to add the location of a missing site to the Voronoi diagram
  • This will mean using the given edge of one or two of the regions and finding the second site that would make this edge a perpendicular bisector
    • Draw a perpendicular line from the site to the edge
    • Check the distance of this line and then continue it on the other site of the edge for the same distance
    • This will be the location of your new site
  • You may need to find the gradients of the edges you have and then use the negative reciprocal to find the gradient of the perpendicular bisector of the current and new site

What is a Voronoi diagram used for?

• Voronoi diagrams are often used in land management to work out where the best location would be according to where sites are already situated
• They can show where to put something to make sure that it is
  • Closest to a particular site
  • Closer to one site than another
  • Equidistant from two or three specific sites
  • As far as possible from any other site

What do I need to know about Voronoi diagrams?

• You may be asked to find the shortest distance from a point to its closest site
  • Use Pythagoras’ Theorem to find the distance between the given coordinate and the site in the same region as it
  • If the coordinate is on an edge then there will be two sites equidistant from it
• You may be asked to find the point which is furthest from any of the sites
  • This will be one of the vertices
  • To choose which vertex look at which is the centre of the largest empty circle
• You may be asked to estimate the success of a new site
  • This is done by looking at the data for the nearest site
  • The prediction for the new site would be assumed to be the same
    • This is called nearest neighbour interpolation