Perimeters of Polygonal Voronoi Cells

A few months ago, a friend of mine (hi Torque!) wrote a blog post about the average perimeters of cells in an N-dimensional Voronoi diagram. I tried following along on the blog post, but was not smart enough to follow their crazy math. I later had a chance to visit them in real life, and got them to sit down with me and go through their math step by step.

I now understand what their math does, and I think it's super cool that they were able to solve this problem not just in 2 dimensions, but in any number of dimensions. However, I still think their way of solving it is a bit difficult to follow, so I came up with my own explanation (currently only written for 2 dimensions but easily altered to any number of dimensions) that I think is easier to understand. This is basically just the same two integrals that Torque used, but with their order swapped and a slight change of variables, so the credit definitely goes primarily to Torque for this one! Also, I assume that readers of this blog post are generally familiar with Torque's blog post and the general problem statement as I will not restate some of the background.

First, let's define the problem. Instead of dealing with an approximation of the perimeter within a \(1\times1\) region, we deal instead with the entire 2D plane, with nodes distributed independently at random with a density \(n\) (an expected \(n\) nodes in each \(1\times1\) region). We will try to find the expected perimeter of the cell around a randomly chosen node.

We assert that for any region of area \(V\), the probability that it is empty is \(e^{-nV}\). See Torque's post for a bit of justification of this fact.

Expected length of line segment between two nodes

Let us pick two nodes in our voronoi diagram. We want to calculate what the expected length of the line segment is between them (by "line segment between them" I mean the locus of points on the plane which are equidistant from our two chosen nodes, and which are not closer to any other node in our voronoi diagram). If our nodes are very close together, then intuitively it is very likely that they will have a non-zero length line segment between them. Meanwhile, if they are far away, there likely lots of other nodes in between, so the length of the line segment is likely to be zero. Let us quantify the expected length now.

Let's give things names. Let's say our chosen nodes are \(A\) and \(B\), and let's say they are at a distance of \(x\) apart. Now, consider a point \(C\) chosen on the perpedicular bisector of \(AB\). Let's say the linear distance between \(C\) and the midpoint between \(A\) and \(B\) is \(y\). Refer to the following diagram:

\(C\) is a contender for being part of the line segment between \(A\) and \(B\), if and only if there are no other nodes closer to \(C\) than \(A\) and \(B\) are. But this is equivalent to checking that there are no other nodes within the circle in the diagram, whose radius is \(\sqrt{\frac{x^2}{4}+y^2}\). This means that the probability that \(C\) is in our segment is: \[e^{-\pi n \left(\frac{x^2}{4}+y^2\right)}\]

We now simply integrate over \(y\) to get the expected length of this line: \[\int_{-\infty}^{\infty}e^{-\pi n \left(\frac{x^2}{4}+y^2\right)}dy = \frac{e^{-\pi n x^2/4}}{\sqrt{n}}\]

Setting \(n=1\), this curve drops off as follows, which lines up with our intuition!

Expected perimeter of a given node

Now, let's try to find the total perimeter of a chosen node \(A\). To do that, we need to sum up all of the lengths of the line segments between \(A\) and every other node in our infinite space. To do that, we do an integral, this time over distances away from \(A\). We can think of it like this: for a given distance range from \(r\) to \(r+dr\), how many nodes can we expect to find, and how much will each contribute to our total perimeter?

The second question we have already answered. It will be \(\frac{e^{-\pi n r^2/4}}{\sqrt{n}}\).

The first question is just a matter of finding the area of each ring of radius \(r\) and thickness \(dr\), and multiplying by our density \(n\) -- it's just \(2\pi rndr\)!

Now we integrate: \[\int_{0}^{\infty}2\pi rn\frac{e^{-\pi n r^2/4}}{\sqrt{n}}dr = \frac{4}{\sqrt{n}}\] and voila! We have our result!

If you liked this post, you might like a follow-up I wrote about a related problem regarding Voronoi diagrams!

Addendum: More dimensions

This same approach can just as easily be used to calculate the expected surface area of a given voronoi cell in higher dimensions, but it just doesn't end up as nice as our 2D result. You end up needing to integrate over \(e^{-\pi n x^{p}}\) for higher values of \(p\), which doesn't typically evaluate into something particularly nice. Additionally, the formulas for the coefficients for surface area and volumes of higher dimensional spheres/balls get kind of crazy, though that's just a constant you can multiply by at the very end.