3
$\begingroup$

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?

1 Answers 1

6

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 $

  • 3
    Easier: Let $\deg(f)$ be the number of edges of face $f$. Then $\sum_f \deg(f) = 2e \le 6n-12$ by Euler's formula. The pigeonhole principle now implies that at least one face $f$ has \deg(f) < 6.2012-03-05