Voronoi Part 2: Lengths of Boundaries

If you have not yet read the first part, go read it here first.

While working through the Voronoi cell perimeter problem in the infinite 2D plane case, I was thinking about ways to get an estimate for the average perimeter within a bounded 1x1 square instead, as was the original problem posed in the YouTube video linked on Torque's blog page. This blog post will follow a line of reasoning that I followed on one attempt to get a better estimate for the bounded Voronoi perimeter problem, which ultimately did not help with getting a better estimate, but which I found to be a rather interesting result regardless.

Problem Description

Suppose we have a Voronoi diagram in infinite 2D space just like in my original post. Suppose now that we divide our space along some line (for simplicity, we can call it the Y axis). We can look only at the subset of the perimeters of our cells which are equidistant from points on either side of our dividing line. I will refer to this collection of line segments as the boundary. This will look as follows, where the dotted line is our dividing line.

I wanted to find what the ratio is between the length of this boundary and the length of the dividing line. Of course, we are dealing with infinite quantities here, so to be slightly more precise, let's define \(B(a, b)\) to be the expected length of the portion of the boundary whose y coordinate is in the range \((a, b)\). We are trying to find \[\lim_{a\rightarrow \infty}\frac{B(-a, a)}{2a}\]

Length Between Two Nodes

First, notice that for any pair of points \(A\) and \(B\), with \(A\) and \(B\) on opposite sides of the dividing line, the entirety of the segment between them will be on our boundary, and conversely, our boundary is exactly the collection of such segments. Also, from the original blog post, we found that the expected length of the segment between two points is exactly \(\frac{e^{-\pi n x^2/4}}{\sqrt{n}}\), where \(x\) is the distance between \(A\) and \(B\).

Integration Time

Now, let \(A=(x_A, y_A)\) be a point whose \(x\) coordinate is negative, meaning that it is on the left of the dividing line at a distance \(x_A\) from it. We will calculate the expected total length of \(A\)'s perimeter which is on the boundary. Without loss of generality, let's assume \(y_A=0\), so we don't have to deal with linear translations of variables. Unlike in the original blog post, we cannot integrate over \(r\), the distance away from \(A\), because we only want to consider points to the right of the dividing line. Instead, we will have to do a double integral over the area on the right of the line: \[\frac{1}{\sqrt{n}}\int_{0}^{\infty}\int_{-\infty}^{\infty}ne^{-\pi n \frac{(x_A+x)^2 + y^2}{4}}dydx = 2\int_{0}^{\infty}e^{-\pi n\frac{(x_A+x)^2}{4}}dx\]

Actually, at this stage doing this integral is hard, so we leave it unintegrated for now.

Integrating Over \(A\)s

Now we need to integrate over the probability distribution of points \(A\) on the left of the line. (As a kind of hack, I only integrate over x values, and not over y values. This function is constant with respect to y, so we don't really need to worry about that, only multiplying by whatever the size of the range of y values we want to consider. But since our original limit \(\lim_{a\rightarrow \infty}\frac{B(-a, a)}{2a}\) divides by the range of y values anyway, they cancel out.) \[\int_0^\infty 2n\int_{0}^{\infty}e^{-\pi n\frac{(x_A+x)^2}{4}}dxdx_A\]

A change of variables (let \(u=x+x_A\)) and some simplification later... \[2n\int_0^\infty ue^{-\pi n\frac{u^2}{4}}du = \frac{4}{\pi}\]

Woah! \(\pi\) showing up unannounced, out in the wild!

1x1 Voronoi Perimeter Problem Application?

I initially thought I could use this result to estimate the total perimeter within a \(1\times1\) bounded square Voronoi diagram more accurately. I thought I could calculate the expected sum of the perimeters of the \(n\) cells within the square, subtracting \(4\frac{4}{\pi}\) from that to account for the loss of the boundary perimeter on each of the \(4\) sides, and then add \(4\) for the new straight boundaries introduced from the bounds of the square region. As it turns out, I believe this approximation of \(4\sqrt{n}-\frac{16}{\pi}+4\), or \(\frac{4\sqrt{n}-\frac{16}{\pi}+4}{n}\) per cell, is even further from the simulated values that Torque calculated (but I will wait for them to verify). So, I guess this approach is not so useful for estimating bounded Voronoi diagram perimeters, but at least I think it's cool on its own right!