6
$\begingroup$

Consider a random voronoi pattern with a uniform distribution on a large flat torus. What are the average number of sides of a cell. My guess is 6.

What about 3D or 4D?

My guess for 4D would be 24. For 3D I'm guessing somewhere between 12 and 13.

Is there a way to work this out?

P.S. I suppose this also depends on which "average" you are using. I'm thinking of the mean.

$\endgroup$
6
  • $\begingroup$ Interesting question. Is it known for a square or a sphere? It's not obvious to me why it would not depend on the particular dimensions of the torus. $\endgroup$ Jan 25, 2019 at 5:33
  • $\begingroup$ @Jair I would consider the torus dimensions so big as to be essentially infinite. $\endgroup$
    – zooby
    Jan 25, 2019 at 5:38
  • $\begingroup$ Then why would it differ from a plane? I guess it wouldn't. $\endgroup$ Jan 25, 2019 at 9:22
  • $\begingroup$ (Except that you can't have a uniform distribution on a plane, of course, since it is infinite.) $\endgroup$ Jan 25, 2019 at 9:53
  • $\begingroup$ @Ivan Probably wouldn't differ but one could do computer simulations with the first and not with the second. $\endgroup$
    – zooby
    Jan 25, 2019 at 16:15

1 Answer 1

6
$\begingroup$

Poisson-Voronoi tessellation. Consider the point process on the $d$-dimensional torus, where each point is uniformly distributed given the total number of points. As the size of the torus goes to infinite while the expected number of uniform points per area converges to some positive number, the point processes converge in distribution to the homogeneous Poisson point process on $\mathbb{R}^d$. (This is a simple generalization of the law of rare events.)

  • The case of $d = 2$. Now consider the planar case ($d=2$) and the Voronoi tessellation associated to this point process. Then with probability one, the planar graph obtained by this Voronoi tessellation is $3$-regular, and so, a typical Poisson-Voronoi cell has $6$ sides, see the addendum below. (Basically $6$ is the 'spatial average' of the number of edges of cells, but this also becomes average number of a typical Poisson-Voronoi cell by ergodicity.)

  • The case of $d=3$. It is known by Meijering (1953)[1] that the average number of vertices of a typical cell is $\frac{96}{35}\pi^2 \approx 27.07$. Then the number of edges is $\frac{3}{2}$-times of the number of vertices, hence is $\frac{144}{35}\pi^2 \approx 40.61$. Finally, by Euler's formula, the average number of faces is $\frac{48}{35}\pi^2 + 2 \approx 15.54$.

[1] Meijering, J. L. (1953). Interface area, edge length, and number of vertices in crystal aggregates with random nucleation. Philips Res. Rep. 8.


Addendum - a simple fact about $3$-regular planar graph. Consider any $3$-regular planar graph $G = (V, E)$ in the torus, where $V$ is the vertex-set and $E$ is the edge-set. If $F$ denotes the set of faces of $G$, then

  • By counting the number of all pairs $(v, e)$ in $V\times E$ for which $v$ is an end-point of $e$ in two ways, we have $2|E| = 3|V|$.

  • For each $f \in F$, let $e_f$ denote the number of edges of $F$. As before, counting the number of pairs $(e, f)$ in $E \times F$ for which $e$ is an edge of $f$, we obtain $\sum_{f\in F} e_f = 2|E|$.

  • Since the Euler characteristic of the torus is $0$, we have $|V| - |E| + |F| = 0$.

Combining altogether, we obtain

$$ \sum_{f\in F} e_f = 6|F|. $$

In other words, the average number of the edges of a face chosen uniformly at random is $6$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .