Virulent Voronoi

This week, I was reading some background for my research, and I learned about something called a Voronoi pattern, which caught my attention. The basic idea is that for a set of points, you divide space into cells based on which point they're closest to. It's connected to my research because we compare incoming signals to a finite set of templates. When we say a particular template is the closest match for a signal, we want to know how far away it could be, i.e. the space spanned by that template.

Voronoi patterns appear in nature frequently – One way to make the pattern for a set of points is to expand each point in a circle, until they collide, which is exactly what would happen if you put several bacterial cultures in a Petri dish. Pixar animators use them to design scale patterns and other natural formations:

What interested me was using different measures of distance, not just the Euclidean distance to find the "closest" point. I wrote up a Python script to make these plots for a set of points, and a given distance measure. There are some really clever ways to make these diagrams, but I took a brute-force approach of dividing the space into a grid, and finding the nearest point for each box. For distance measures, I used the usual Euclidean distance, the metropolitan or taxi-cab metric, and the relativistic spacetime interval.

Euclidean Distance
This is the usual distance measure you probably learned in high school. A straight line between two points has a length of

For a random set of 5 points, we can divide a space into regions based on which point they're closest to.

Set 1, Euclidean

Set 2, Euclidean

Metropolitan Distance
You don't always want to measure distance with straight lines though. In a city, the streets are laid out in a grid, so you always have to move at right angles. In this case we just sum the vertical and horizontal differences:

 

For the same two sets of points, this gives some very different regions.

Set 1, Metropolitan

Set 2, Metropolitan

Spacetime Interval
In special relativity, there's a quantity called the spacetime interval, which gives properties of a path through spacetime. In this case, we usually work with the square:

Here c is the speed of light, which puts time and space into the same units. If this quantity is positive, the path is called time-like, and could describe a massive particle's motion. If it's negative, the path is called space-like, which means the two points can only be connected by faster than light motion. Relativity assumes this is impossible, so a space-like curve can't describe motion. Finally, if the interval is zero, it describes a beam of light, since Δx/Δt = c.

If we look for the minimum positive spacetime interval for each point, we can apply the idea of a Voronoi pattern to relativistic motion. First an example with just 2 points, to see what kind of patterns this creates.

Example Spacetime

Time is along the vertical axis, and x is horizontal. Each point projects a region above and below. If we think of the points as observers, the regions represent positions and times for which that point is the first to see what happened there (or for points ahead of the observer, the first place they are observed). White areas show events that no observer can witness.

Keeping all that in mind, we can look at the previous two point sets under this metric.

Set 1, Spacetime

Set 2, Spacetime

These are a bit of a mess, but it's an interesting way to look at the spacetime interval. In the second set, there are several narrow slivers due to the metric favoring light-like (45° diagonal) paths.

I'm not sure this is useful for anything aside from making interesting pictures, but that's good enough for me!