5
$\begingroup$

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.

$\endgroup$

2 Answers 2

10
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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{}$ $\endgroup$ May 25, 2014 at 20:19
  • $\begingroup$ 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. $\endgroup$ May 25, 2014 at 20:26
  • 2
    $\begingroup$ 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.") $\endgroup$ May 25, 2014 at 21:31
  • $\begingroup$ 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. $\endgroup$ May 26, 2014 at 2:17
  • 1
    $\begingroup$ Do we think this is true? www-cs-students.stanford.edu/~amitp/game-programming/… $\endgroup$ May 26, 2014 at 7:43
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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