Drawing Voronoi Diagrams (DP IB Applications & Interpretation (AI)): Revision Note

Drawing 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