Content
Properties of Voronoi Diagrams
What a Voronoi diagram is, perpendicular bisectors, terminology and construction.
What a Voronoi diagram is, perpendicular bisectors, terminology and construction.
No exercises available for this concept.
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:
Powered by Desmos
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
Powered by Desmos
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.
Powered by Desmos
The vertices of a Voronoi diagram are equidistant from the generating sites whose cells they border.
Powered by Desmos
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.