# “Average” Voronoi diagrams without probability?

A plane Poisson process with uniform intensity scatters "sites" about the plane. If I'm not mistaken, in a sense the "average" Voronoi diagram of that set of sites is a honeycomb. I know it's been proved that the average number of edges of the cells is $6$, and I've read (but not in anything published very recently) that the probabilities that the number of edges is equal to $n$ for $n\in\{3,4,5,\ldots\}$ is known only numerically.

My question is whether there is any sense in which the average shape could be said to be a honeycomb or the number of edges in an average Voronoi diagram can be shown to be $6$ without any sort of probability distribution on the set of sites?

This is a vague hunch which I suspect was inspired in part by the time I read in Seymour Geisser's book on predictive inference a way of deriving Student's small-sample confidence intervals without using probability. Although probability was not mentioned, the squaring function as an objective function was relied on.

-

Here is an argument that Béla Bollobás showed me once. (this was motivated by a physics paper where a simulation was done showing that the average number of edges per face was 5.997$\pm$ 0.005).

Take a large number of seeds (i.e. points generating the Voronoi diagram) and make the assumption that there are no multiple points: points of that are simultaneously closest to four or more seeds. (This is certainly the case with probability 1 if the seeds come from a Poisson Processes, but of course it's much more general than that).

Then use Euler's formula. Each vertex of the Voronoi diagram is nearest to exactly three seeds. Each of the $\binom 32$ pairs of seeds gives an edge in the Voronoi diagram, so that each vertex has three edges emanating from it. Let $v$ be the number of vertices, $e$ be the number of edges and $f$ the number of faces. Then $f-e+v=2$ by Euler's formula. Also $2e=3v$, so that $f=2+\frac e3$. Let $\rho$ be the average number of edges per face. Then $e=\rho f/2$, so that $f=2+\rho f/6$. Hence when the number of faces becomes large, the number of edges per face approaches 6.

-
So the ONLY thing we need is the "general position" assumption that there are no points where more than three cells meet$\ldots\ldots$(?) ${}\qquad{}$ – Michael Hardy May 25 '14 at 20:19
I guess the error in this approximation arises from the "vertices at infinity" which do not have degree 3. On the sphere it should be exact, I think. – Nate Eldredge May 25 '14 at 20:26
Another reason why to expect a geometric argument (codified here in the genus 0 case of Euler's formula) is that the number of edges is less than, equal to, or greater than 6 depending on the sign of the curvature. ("A random Voronoi soccer ball will have more pentagons than heptagons.") – Steve Huntsman May 25 '14 at 21:31
OK, can anyone say something about the other part of my question, about the average shape being a honeycomb? I don't know any precise definition of "average shape", so that's another difficulty. – Michael Hardy May 26 '14 at 2:17
Do we think this is true? www-cs-students.stanford.edu/~amitp/game-programming/… – Anthony Quas May 26 '14 at 7:43

There is a theorem [in a short three author manuscript to be posted soon on archive] that proves: Given any decomposition of the plane into topological cells satisfying a rather weak geometric condition, the average number of sides in a scaled up region of reasonable shape is defined in the limit and equal to a number at most six. The geometric condition is: each cell has a diameter bounded from above and each cell has an area bounded from below. Each condition is necessary [examples of Chris Bishop at Stony Brook math]. Also in 3D there are convex cell decompositions with arbitrarily large average face numbers with all of the interior bodies congruent.[example of Mike Wigler Cold Spring Harbor Labs] third author Dennis Sullivan

-