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?
yrealeq
Answered question
2022-09-11
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?
Answer & Explanation
Vicente Macias
Beginner2022-09-12Added 15 answers
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 . The Euler characteristic is also given by , where , , and are the number of vertices, edges, and faces in the Delaunay triangulation respectively. Now every face has edges, while all non-boundary edges are adjacent to faces. Under reasonable conditions*, the proportion of boundary edges tends to zero, so let us ignore them. This means that , and plugging this into gives , where by "" I mean the ratio tends to as . So there are about three times as many edges as vertices, and since each edge is incident on vertices, the average degree of the vertices approaches . 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 D case. In three dimensions, the Euler characteristic is still , but is now given by , where is the number of tetrahedral cells in the triangulation. A similar argument as above gives , but we have no control over . 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 D case, every such triangulation had exactly the same number of edges.