The terminology of Voronoi diagrams, including sites, cells, edges and vertices, with edges as perpendicular bisectors, vertices equidistant from three or more sites, adding a new site, nearest neighbor interpolation, and largest empty circle or toxic waste dump problems.
The diagram below shows a city with five airports, and a plane flying in circles in the sky above it. The airspace is broken into 5 regions, each representing all the locations where the plane is closer to the airport located in that region than any other airport. If the plane needed to divert for an emergency landing, the pilots would land it at the closest airport possible: a region being highlighted represents the fact that if the plane were in that location when it needed to make an emergency landing, it would divert to airport in the highlighted region.
The above graph is known as a Voronoi diagram. Voronoi diagrams can seem intimidating at first, but in reality, all we need to construct them is a good understanding of lines. We'll walk through the step-by-step construction of one such diagram to get an understanding of what they are and how they work.
To begin our exploration of Voronoi diagrams, we need to define the term perpendicular bisector.
The perpendicular bisector of the line segment, AB, connecting two points A and B, is the line which is perpendicular to AB and also passes through its midpoint M. All the points on the perpendicular bisector of AB are the same distance from A and B.
You can find the equation of a perpendicular bisector in point-gradient form by using the midpoint of AB
as the point, and setting the gradient equal to the negative reciprocal of the gradient of AB, denoted mAB:
The following terminology is used to refer to different parts of a Voronoi diagram:
The points that we construct the diagram around are called sites, or sometimes generating sites
The regions formed by all the points closest to any one site (highlighted in different shades of blue below) are called cells
The dividing lines between cells, where points are equidistant from two generating sites, are known as edges
The points where multiple edges meet, which are equidistant from three or more generating sites, are called vertices
Every edge in a Voronoi diagram is the perpendicular bisector of the two sites that it separates (the sites whose cells are on either side of the edge).
This means that given one of two sites and the equation of the perpendicular bisector (edge), we can find the second site. Similarly, given two sites, we can find the equation of the edge between them by finding their perpendicular bisector.
We can add a new site to a Voronoi diagram using the following process:
Find the closest existing site to the new site.
Find the midpoint of these this site and the new site.
Draw the perpendicular bisector between these two points until you reach an existing edge.
Pick the site in the region where the bisector would continue, and repeat from step 2.
If the bisector does not hit a boundary, erase any original edges enclosed within the newly added edges.
The vertices of a Voronoi diagram are equidistant from the generating sites whose cells they border.
Each vertex can be seen as the center of a circle determined by three or more sites. It is possible for a vertex to be at the intersection of more than three cells and therefore be the center of a circle with four or more sites on it, but not necessary.
Nice work completing Properties of Voronoi Diagrams, here's a quick recap of what we covered:
Exercises checked off
The terminology of Voronoi diagrams, including sites, cells, edges and vertices, with edges as perpendicular bisectors, vertices equidistant from three or more sites, adding a new site, nearest neighbor interpolation, and largest empty circle or toxic waste dump problems.
The diagram below shows a city with five airports, and a plane flying in circles in the sky above it. The airspace is broken into 5 regions, each representing all the locations where the plane is closer to the airport located in that region than any other airport. If the plane needed to divert for an emergency landing, the pilots would land it at the closest airport possible: a region being highlighted represents the fact that if the plane were in that location when it needed to make an emergency landing, it would divert to airport in the highlighted region.
The above graph is known as a Voronoi diagram. Voronoi diagrams can seem intimidating at first, but in reality, all we need to construct them is a good understanding of lines. We'll walk through the step-by-step construction of one such diagram to get an understanding of what they are and how they work.
To begin our exploration of Voronoi diagrams, we need to define the term perpendicular bisector.
The perpendicular bisector of the line segment, AB, connecting two points A and B, is the line which is perpendicular to AB and also passes through its midpoint M. All the points on the perpendicular bisector of AB are the same distance from A and B.
You can find the equation of a perpendicular bisector in point-gradient form by using the midpoint of AB
as the point, and setting the gradient equal to the negative reciprocal of the gradient of AB, denoted mAB:
The following terminology is used to refer to different parts of a Voronoi diagram:
The points that we construct the diagram around are called sites, or sometimes generating sites
The regions formed by all the points closest to any one site (highlighted in different shades of blue below) are called cells
The dividing lines between cells, where points are equidistant from two generating sites, are known as edges
The points where multiple edges meet, which are equidistant from three or more generating sites, are called vertices
Every edge in a Voronoi diagram is the perpendicular bisector of the two sites that it separates (the sites whose cells are on either side of the edge).
This means that given one of two sites and the equation of the perpendicular bisector (edge), we can find the second site. Similarly, given two sites, we can find the equation of the edge between them by finding their perpendicular bisector.
We can add a new site to a Voronoi diagram using the following process:
Find the closest existing site to the new site.
Find the midpoint of these this site and the new site.
Draw the perpendicular bisector between these two points until you reach an existing edge.
Pick the site in the region where the bisector would continue, and repeat from step 2.
If the bisector does not hit a boundary, erase any original edges enclosed within the newly added edges.
The vertices of a Voronoi diagram are equidistant from the generating sites whose cells they border.
Each vertex can be seen as the center of a circle determined by three or more sites. It is possible for a vertex to be at the intersection of more than three cells and therefore be the center of a circle with four or more sites on it, but not necessary.
Nice work completing Properties of Voronoi Diagrams, here's a quick recap of what we covered:
Exercises checked off