12
$\begingroup$

Consider a large set of points with coordinates that are uniformly distributed within a unit-length segment. Consider a Voronoi diagram built on these points. If we consider only non-infinite cells, what would be (if any) the typical (most frequent) number of edges (that is, neighbors) for those cells? Is there a limit for this number when number of points goes to infinity? Does it have anything common with kissing number? If so, doest it generalize to higher dimensions, that is, 6 for 2D, 13 for 3D etc?

2 Answers 2

-1

I think the book Spatial tessellations : concepts and applications of Voronoi diagrams by OKABE, BOOTS,and SUGIHARA discusses this.

  • 1
    Perhaps a bit late, but the book is on Google Books. Page 65, property V13 reads: "The average number of Voronoi edges per Voronoi polygon does not exceed 6". I interpret this as "Given sufficient verteces and no special cases, the average number of neighbors of a cell approaches 6.", because it's quite easy to pick special cases where the number is drastically lower, while my randomly generated tests seem to return ~6.2014-06-05
1

I don't have access to the book that @lhf referenced, but here is a nice topological argument for the expected number of edges of a Voronoi cell in $2$D. Unfortunately, it does not generalize to more than two dimensions.

Consider the dual of the Voronoi diagram, which is the Delaunay triangulation of the given points. This is a planar connected graph, so its Euler characteristic is $\chi = 2$. The Euler characteristic is also given by $\chi = V - E + F$, where $V$, $E$, and $F$ are the number of vertices, edges, and faces in the Delaunay triangulation respectively. Now every face has $3$ edges, while all non-boundary edges are adjacent to $2$ faces. Under reasonable conditions*, the proportion of boundary edges tends to zero, so let us ignore them. This means that $3F \approx 2E$, and plugging this into $V - E + F = 2$ gives $V \approx \frac13E + 2$, where by "$\approx$" I mean the ratio tends to $1$ as $V \to \infty$. So there are about three times as many edges as vertices, and since each edge is incident on $2$ vertices, the average degree of the vertices approaches $6$. As the degree of a vertex in the Delaunay triangulation is precisely the number of edges of the corresponding Voronoi cell, this agrees with your intuition for the $2$D case. (Although, strictly speaking, the expected number of edges is not the same as the most frequent number of edges).

In three dimensions, the Euler characteristic is still $2$, but is now given by $V - E + F - C$, where $C$ is the number of tetrahedral cells in the triangulation. A similar argument as above gives $4C \approx 2F$, but we have no control over $E$. Indeed, there are triangulations on the same point set with the same boundary (the convex hull) but which have different numbers of edges. In the $2$D case, every such triangulation had exactly the same number of edges! So in $3$D one will have to think about the geometry of the Voronoi diagram and/or Delaunay triangulation, and cannot get a result purely via its topology.


* I believe it is sufficient for the points to be drawn from a uniform distribution on a strictly convex area, but I don't know the details.

  • 0
    Bit late response, but in case someone is still interested, here's my comment of the other post: Perhaps a bit late, but the book is on Google Books. Page 65, property V13 reads: "The average number of Voronoi edges per Voronoi polygon does not exceed 6". I interpret this as "Given sufficient verteces and no special cases, the average number of neighbors of a cell approaches 6.", because it's quite easy to pick special cases where the number is drastically lower, while my randomly generated tests seem to return ~6.2014-06-05