Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer
    
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 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 at 20:26
2  
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 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 at 2:17
1  
Do we think this is true? www-cs-students.stanford.edu/~amitp/game-programming/… –  Anthony Quas May 26 at 7:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.