Voronoi Diagrams
Example Problem
Look at the Voronoi diagram below. Each site (A,B,C,D) represents the location of a Coffee Shop
Investigating Questions
1. What is the significance of the cells being bounded by the perpendicular bisectors between the sites?
2. Susie is looking for the closest coffee shop. She is current at the point (9,5). Which shops should she go to?
3. The next day, she is at (2,3). Which shops should she go to?
Example Problem 2
Imagine a town has five fire stations.To minimize response time to a fire, each fire station should respond to fires in its region. How do we determine the boundaries of the regions?
Create your own Voronoi Diagram
Is a Voronoi Cell Convex?
Yes, A Voronoi region is defined by a set of half-planes: The Voronoi region for A, denoted V(A), consists of all the points x in the plane that are closer to A than to any other site B.The intersection of convex sets (half-planes) is itself convex. Therefore, Voronoi regions are convex.
What if you have three sites that are collinear?
Theorem
A Voronoi diagram with at least three sites has an infinite line if and only if all the sites are collinear.
Proof:
If the Voronoi diagram has an infinite edge, then the sites are collinear.
Let’s assume there is an infinite Voronoi edge between sites AAand BB.
This edge lies on the perpendicular bisector of AB‾\overline{AB}, and part of it extends infinitely in both directions.
So if the edge is infinite, then no other site C lies in a position to interfere with the bisector between A and B. That only happens when all other points lie on the line through A and B(so the perpendicular bisector isn’t “blocked”). Thus, the sites are collinear.
If all sites are collinear, then the Voronoi diagram has at least one infinite edge.
Suppose A1,A2,…,AnA_1, A_2, \dots, A_n are all on a line (say, the xx-axis).Then
- The perpendicular bisectors between neighboring sites are all vertical lines (perpendicular to the line the points lie on).
- The two outermost regions (for the leftmost and rightmost sites) will have no neighboring sites on one side.
- Their Voronoi edges will extend infinitely outward.
- You always get infinite rays on the leftmost and rightmost edges.
- In fact, every Voronoi region becomes an infinite vertical strip or ray. Therefore, the Voronoi diagram must have infinite edges.
What happens if you add another site?
Investigating Question to form Intution
- What kind of pattern do you notice as you add more sites?
- Does every new site create lots of new edges/vertices?
- Do the number of edges or vertices ever exceed 3n−63n - 6or 2n−52n - 5?
Intuition For Proof
Voronoi diagram is a planar graph (no edges cross).Using Euler’s formula:
V−E+F=2
where F=n (1 region per site,n).
Theorem
A Voronoi diagram with n sites, where n > 3, has at most 3n — 6 Voronoi
edges and at most 2n — 5 Voronoi vertices.
Proof
For any connected planar graph: V−E+F=2
In our case, the Voronoi diagram has:
- V Voronoi vertices
- E Voronoi edges
- F=n Voronoi cells (faces)