This post is about a generalization of Voronoi diagram that I played around with. It’s probably not that useful but it’s a little fun math with an absolute ton of colorful diagrams.

It occurred to me a while ago that there was a generalization of Voronoi diagrams that maybe could be useful to something I was working on. As you know, a Voronoi diagram divides the plane into regions based on a set of points. Given the points, *p _{0}*,

*p*, …,

_{1}*p*, the region corresponding to

_{n}*p*is the set of points that are closer to

_{i}*p*than any of the other

_{i}*p*. Here is an example of a run-of-the mill, standard, plain vanilla, Voronoi diagram:

_{j}This diagram determines which points are closer using normal, cartesian, distance but Voronoi diagrams also make sense for other kinds of distance, for instance Manhattan distance:

The generalization that occurred to me was: if a region in a plain Voronoi diagram is defined by the one point it is closest to, what if you defined a diagram where regions are based on the two closest points? That is, for each pair of points, *p _{i}* and

*p*, there would be a region made up of points where the closest point is

_{j}*p*and the second-closest is

_{i}*p*. What would that look like, I wondered. I searched around and it’s definitely a thing, it’s called a higher-order Voronoi diagram, but I couldn’t find any actual diagrams.

_{j}There may be some established terminology around this but I ended up using my own names: I would call what I just described a Voronoi^{2} diagram, and a plain one would be a Voronoi^{1}. (From here on I’ll call the region around *p _{i}* in the Voronoi

^{1}diagram

*V*(

*p*), and the region around

_{i}*p*and

_{i}*p*in the Voronoi

_{j}^{2}diagram I’ll call

*V*(

*p*,

_{i}*p*)).

_{j}You can kind of guess just from the definition that a Voronoi^{2} would look similar to the corresponding Voronoi^{1} just more subdivided. For any given *p _{i}*, the point’s region in the Voronoi

^{1}diagram,

*V*(

*p*), is the set of point closest to

_{i}*p*. Well for any point in that set they will have some other point

_{i}*p*as their second-closest, and so if you take the union over all

_{j}*p*of

_{j}*V*(

*p*,

_{i}*p*) that gives you

_{j}*V*(

*p*). So the regions in a Voronoi

_{i}^{2}diagram are basically fragments of regions of the Voronoi

^{1}.

Below is the same diagram as before, for comparison, and the Voronoi^{2} diagram.

As you can see, that is exactly what the Voronoi^{2} diagram looks like: each Voronoi^{1} region has been subdivided into sub-regions, one for each of its neighboring points. You can do the same thing for the Manhattan diagrams,

Now we’ve defined Voronoi^{1} and Voronoi^{2} but why stop there when we could keep going and define Voronoi^{3}. This would be, you’ve probably already guessed it, a diagram with a region for each choice of *p _{i}*,

*p*, and

_{j}*p*, that is made up of the points that have

_{k}*p*as their closest point,

_{i}*p*as their second-closest, and

_{j}*p*as their third-closest. Let’s call such a region

_{k}*V*(

*p*,

_{i}*p*,

_{j}*p*). As I’m sure you’ve already guessed the Voronoi

_{k}^{3}regions are further subdivisions of the Voronoi

^{2}regions:

And the Manhattan version,

The images are becoming smaller but you can click them to see larger versions.

From here you can just keep going: Voronoi^{4}, Voronoi^{5}, Voronoi^{6}, and so on and so on. Which of course I did, what did you expect? Here are Voronoi^{1}-Voronoi^{8} with cartesian distance,

and the same with Manhattan distance

Except… I lied before when I said you could just keep going. In this example there are 8 points so the Voronoi^{n} diagrams are only well-defined for *n* up to 8 – that’s why there’s 8 diagrams above. And indeed if you look closely diagram 7 and 8 are actually the same – because once you’ve picked 7 points there is no choice for the last point, there is only the 8th left, so the diagrams end up looking exactly the same.

So is that it – is that all the colorful diagrams we get? Well, there is just one last tweak we can make to get a different kind of diagram.

The thing is, in the definition of Voronoi^{2} we said that *V*(*p _{i}*,

*p*) was the points where

_{j}*p*is the closest point and

_{i}*p*is the second-closest. That is, the order of

_{j}*p*and

_{i}*p*is significant. An alternative definition we could use would be one where we don’t consider the order, where the region doesn’t care whether it’s

_{j}*p*closest and

_{i}*p*second-closest, or

_{j}*p*closest and

_{j}*p*second-closest. I’ll call this

_{i}*V*(

_{u}*p*,

_{i}*p*) (the

_{j}*u*is for unordered).

You’ll notice right away that by this definition *V _{u}*(

*p*,

_{i}*p*)=

_{j}*V*(

_{u}*p*,

_{j}*p*) so there’s a lot fewer regions. Here’s an example of a Voronoi

_{i}_{u}

^{1}(which is the same as the Voronoi

^{1}) and Voronoi

_{u}

^{2}diagram,

With these unordered diagrams it can be a little trickier to figure out which two points a region actually corresponds to, especially in cases where the points in question are far away from the region. The trick you can use in this case is that for a given region is in the Voronoi_{u}^{2}, if you look at the same place in the Voronoi^{1} there will be a dividing line that goes across where the region is in the Voronoi_{u}^{2}, from one corner of the region to another. The two points on either side of the Voronoi^{1} will be the one the region corresponds to.

The same things works, as always, with Manhattan distance:

An interesting thing happens if we plot all the Voronoi_{u}^{n} all the way up to 8:

The number of regions stays about the same and when we get to Voronoi_{u}^{7} and Voronoi_{u}^{8} they actually become simpler. This is because at that point the set of points for a given region includes almost all the points so the determining factor becomes which are the few points that aren’t in the set – and at 7 and 8 there’s 1 and 0 left respectively. So whereas Voronoi^{8} was useless because it’s the same as Voronoi^{7}, here it’s useless because there’s only one region that contains all the points.

Is this construction at all useful? I’m not sure, I imagine it could be but I don’t have any particular use for them myself. Really I was just curious what it would look like.

I’ll leave you with a last set of diagrams, Voronoi_{u}^{1} to Voronoi_{u}^{8} for Manhattan distance.