Topics
Track your progress across all skills in your objective. Mark your confidence level and identify areas to focus on.
Track your progress:
Don't know
Working on it
Confident
📖 = included in formula booklet • 🚫 = not in formula booklet
Track your progress:
Don't know
Working on it
Confident
📖 = included in formula booklet • 🚫 = not in formula booklet
Track your progress across all skills in your objective. Mark your confidence level and identify areas to focus on.
Track your progress:
Don't know
Working on it
Confident
📖 = included in formula booklet • 🚫 = not in formula booklet
Track your progress:
Don't know
Working on it
Confident
📖 = included in formula booklet • 🚫 = not in formula booklet
Track your progress across all skills in your objective. Mark your confidence level and identify areas to focus on.
Track your progress:
Don't know
Working on it
Confident
📖 = included in formula booklet • 🚫 = not in formula booklet
Track your progress:
Don't know
Working on it
Confident
📖 = included in formula booklet • 🚫 = not in formula booklet
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.
Nearest neighbor interpolation is a method for estimating unknown data points based on a Voronoi diagram. If each site is assigned a numerical value, such as the precise temperature at the location of a site, then all other points in that site's cell are also approximated at that value. Points which are equidistant from two are more sites are approximated by averaging the values of the sites it is equidistant from.
Example (temperature):
The graphic shows a heat map overlaid with a Voronoi diagram split into five sections. The generating sites, denoted with black triangles, represent the exact temperatures taken at those locations. Dragging the thermostat around indicates the nearest neighbor approximation (the text on the bottom left) for the location at the thermostat's current position.
The toxic waste dump problem, sometimes referred to as the largest empty circle problem, is a type of question that asks you to identify the farthest location from all other given sites. This is solved by constructing a Voronoi diagram, and the answer to the toxic waste dump problem is always a vertex of the corresponding Voronoi diagram. If there are multiple vertices, the solution is the vertex which is further from its closest sites (the one which is the center of a circle with the largest radius).
In the example above, Q is further from its closest points than P, so the solution to this toxic waste dump problem is the point Q.
This kind of problem may also appear in the context of placing businesses as far as possible from their competitors, or identifying the point at the center of the largest circle that can be drawn on a diagram without containing any of the sites.
Track your progress across all skills in your objective. Mark your confidence level and identify areas to focus on.
Track your progress:
Don't know
Working on it
Confident
📖 = included in formula booklet • 🚫 = not in formula booklet
Track your progress:
Don't know
Working on it
Confident
📖 = included in formula booklet • 🚫 = not in formula booklet
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.
Nearest neighbor interpolation is a method for estimating unknown data points based on a Voronoi diagram. If each site is assigned a numerical value, such as the precise temperature at the location of a site, then all other points in that site's cell are also approximated at that value. Points which are equidistant from two are more sites are approximated by averaging the values of the sites it is equidistant from.
Example (temperature):
The graphic shows a heat map overlaid with a Voronoi diagram split into five sections. The generating sites, denoted with black triangles, represent the exact temperatures taken at those locations. Dragging the thermostat around indicates the nearest neighbor approximation (the text on the bottom left) for the location at the thermostat's current position.
The toxic waste dump problem, sometimes referred to as the largest empty circle problem, is a type of question that asks you to identify the farthest location from all other given sites. This is solved by constructing a Voronoi diagram, and the answer to the toxic waste dump problem is always a vertex of the corresponding Voronoi diagram. If there are multiple vertices, the solution is the vertex which is further from its closest sites (the one which is the center of a circle with the largest radius).
In the example above, Q is further from its closest points than P, so the solution to this toxic waste dump problem is the point Q.
This kind of problem may also appear in the context of placing businesses as far as possible from their competitors, or identifying the point at the center of the largest circle that can be drawn on a diagram without containing any of the sites.