Number of vertices in vornoi diagram

Question

Assuming general position, I want to prove that for a Voronoi diagram of $n$ points, the average number of vertices of a cell is arbitrarily close to $6$ as $n → ∞$.

I am not really sure how I should do it. One possible way is to do it by probabilistic method.

Any help will be appericiated.

See also https://math.stackexchange.com/questions/115292/voronoi-average-number-of-vertices-6/115302 — lhf, Jan 17 '22 at 12:52
@lhf Do you remember why $2e = 3F_3 + 4F_4 + 5F_5 + \cdots$. ? — aaa bbb, Jan 17 '22 at 15:09
Each n-face contributes n edges which are counted twice because of adjacent faces — lhf, Jan 17 '22 at 15:56

score 2 · Answer 1 · answered Jan 17 '22 at 12:24

2

It's not true in general. If the points are arranged in a square grid, the average number of vertices per cell will be 4.

However, for a random set of points, it's true. You can start by proving that the degree of a vertex is almost surely 3. After that you can use the Euler formula for a planar graph.

answered Jan 17 '22 at 12:24

Vasily Mitch

10,129

"It" not true in general" isn't true ! Have you seen that the OP says "points are in general position". – Jean Marie Jan 17 '22 at 21:04

Number of vertices in vornoi diagram

1 Answers1