Look at the Voronoi diagram below. Each site (A,B,C,D) represents the location of a Coffee Shop

1. What is the significance of the cells being bounded by the perpendicular bisectors between the sites?[br][br]2. Susie is looking for the closest coffee shop. She is current at the point (9,5). Which shops should she go to?[br]3. The next day, she is at (2,3). Which shops should she go to?

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?

Yes, [*]A Voronoi region is defined by a set of [b]half-planes[/b]:[math]V\left(A\right)=\left\{x:d\left(x,A\right)\le d\left(x,B\right)\text{for all other B}\right\}[/math] 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 [b]intersection of convex sets (half-planes)[/b] is itself [b]convex[/b]. Therefore, Voronoi regions are convex.[/*]

A Voronoi diagram with at least three sites has an infinite line if and only if all the sites are collinear.

[math]\longrightarrow[/math] [b]If the Voronoi diagram has an infinite edge, then the sites are collinear.[br][/b]Let’s assume there is an infinite Voronoi edge between sites AAand BB.[br]This edge lies on the [b]perpendicular bisector of AB‾\overline{AB}[/b], and part of it extends infinitely in both directions.[br]So if the edge is [b]infinite[/b], then [b]n[/b][b]o other site C [/b]lies in a position to interfere with the bisector between A and B. That only happens when all other points lie [b]on the line through [/b]A[b] and [/b]B(so the perpendicular bisector isn’t “blocked”). Thus, the sites are collinear. [br][math]\longleftarrow[/math][b]If all sites are collinear, then the Voronoi diagram has at least one infinite edge.[br][/b]Suppose A1,A2,…,AnA_1, A_2, \dots, A_n are all on a line (say, the xx-axis).Then[list][*][br]The [b]perpendicular bisectors[/b] between neighboring sites are all [b]vertical lines[/b] (perpendicular to the line the points lie on).[/*][*][br]The two outermost regions (for the leftmost and rightmost sites) will have [b]no neighboring sites[/b] on one side.[/*][*][br]Their Voronoi edges will extend [b]infinitely outward[/b].[/*][/list]So in a collinear configuration[list][*][br]You always get [b]infinite rays[/b] on the leftmost and rightmost edges.[/*][*][br]In fact, every Voronoi region becomes an infinite vertical strip or ray. Therefore, the Voronoi diagram must have infinite edges.[/*][/list]

[list=1][*]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 [b]exceed[/b] 3n−63n - 6or 2n−52n - 5?[br][/*][br][/list][br]

Voronoi diagram is a [b]planar graph[/b] (no edges cross).[*]Using Euler’s formula:[br]V−E+F=2[br]where F=n (1 region per site,n).[/*]

A Voronoi diagram with n sites, where n > 3, has at most 3n — 6 Voronoi[br]edges and at most 2n — 5 Voronoi vertices.

[size=100]For any [b]connected planar graph[/b]: V−E+F=2[br][br]In our case, the Voronoi diagram has:[list][*]V Voronoi vertices[/*][*]E Voronoi edges[/*][*]F=n Voronoi cells (faces)[/*][/list]So:V−E+n=2[br][br]Each Voronoi [b]vertex[/b] is the intersection point of [b]three or more edges[/b] — i.e., the degree of each vertex is at least 3. Each Voronoi [b]edge[/b] connects two such vertices (or extends to infinity), and each edge contributes to the degree count of two vertices.[br][br]So the [b]sum of degrees[/b] (the number of edges that meet at that vertex) over all Voronoi vertices is:[br][math]\text{∑deg⁡(v)≥3V}[/math][br]But this sum is also equal to [b]twice the number of edges[/b] (since each edge has 2 endpoints):[br][math]\text{∑deg⁡(v)=2E⇒2E≥3V}[/math][br]From V=E−n+2 we can substitute this into the above inequality:[br][math]\text{2[br]E[br]≥[br]3[br]([br]E[br]−[br]n[br]+[br]2[br])[br]⇒[br]2[br]E[br]≥[br]3[br]E[br]−[br]3[br]n[br]+[br]6[br]⇒[br]−[br]E[br]≥[br]−[br]3[br]n[br]+[br]6[br]⇒[br]E[br]≤[br]3[br]n[br]−[br]6}[/math][br][br]Now plug [math]\text{E[br]≤[br]3[br]n[br]−[br]6[br]}[/math] into[math]\text{ [br]V[br]=[br]E[br]−[br]n[br]+[br]2}[/math][br][br][math]\text{V[br]≤[br]([br]3[br]n[br]−[br]6[br])[br]−[br]n[br]+[br]2[br]=[br]2[br]n[br]−[br]4}[/math][br]However, [b]a more precise bound[/b] can be obtained because not all Voronoi edges terminate at two finite vertices — some extend to infinity. Each such [b]unbounded edge[/b] reduces the number of finite Voronoi vertices, so: [math]\text{V[br]≤[br]2[br]n[br]−[br]5}[/math]. [br][br]Thus, the maximum edges and vertices a diagram has is [math]3n-6\text{ and }2n-5\text{ respectively, where n is the number of faces or sites.}[/math][/size][code][/code]