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

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

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 χ = 2. The Euler characteristic is also given by χ = 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 3 F 2 E, and plugging this into V E + F = 2 gives V 1 3 E + 2, where by " " I mean the ratio tends to 1 as V . 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 2D case.
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 4 C 2 F, 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 2D case, every such triangulation had exactly the same number of edges.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?