My text says "the average number of vertices of the Voronoi cells is less than six". Then it creates the vertex "at infinity", connects the half-infinite edges to this vertex and shows the equation: $$(v + 1) – e + n = 2$$ where v = number of vertices (before creation of the one at infinity), e is the number of edges, and n is the number of point sites. It then shows the inequality: $$2e \geq 3(v + 1)$$
I've probably been staring at this too long, but how to show the average number of vertices of the Voronoi cells is less than six?
Best Answer
Let $F_k$ be the number of Voronoi cells with $k$ vertices. By counting edges you get $2e = 3F_3 + 4F_4 + 5F_5 + \cdots$. The average you seek is $$ \frac{3F_3 + 4F_4 + 5F_5 + \cdots}{F_3 + F_4 + F_5 + \cdots} = \frac{2e}{n} \le \frac{2(3n-6)}{n}=6-\frac{12}{n} <6 $$
Here I've used that $e\le 3n-6$, which follows from $$ 2(v+n-1) = 2e \ge 3(v+1) \implies v \le 2n-5 \implies e = v+n-1 \le 3n-6 $$