Voroni Diagrams and Graphs III: The Dual.

In this post, I'll write about the geometric significance of the dual of the Voroni graph and try to convince you that we can extend our discussion, which has so far focused on two dimensions, up to three-dimensions with only some minor changes ( I'll conjecture that the relationships I'm about to lay out extend much beyond that, but I don't have much proof of this ).


First, though, we need to discuss what a dual is.


The dual of a graph is itself another graph. Basically every face in the graph is a node in the dual, and two nodes in the dual have an edge between them if ( and only if ) their two corresponding faces share an edge (corners don't count).

The dual of a planar graph is itself a planar graph, and I claim that the dual of the dual of a graph is the graph itself (with the caveat that we discuss in the next paragraph). The figure below hints at a proof for this (note the crossing edges), though I'm not going to formalize it.

Lastly, the dual of a graph is dependent on the layout of the graph. If a graph has two different layouts, and these layouts cannot be stretched into each other (when drawn on a sphere) without edges crossing in the process, then the duals we get from each layout will be very different. These graphs will actually be topologically distinct graphs with different structures.


All of this is to say that when we want to make statements about properties of a dual of a graph, we need to be very careful. We either need to pick a layout, prove that there is only one valid layout, or prove that whatever property we are interested in doesn't depend on the layout. Obviously, the first option is easiest if we can afford it.


In the case of the Voroni graph in 2D, we can simply choose the layout that corresponds to each node of the graph being placed at it's corresponding point in 2-space. For the rest of this post, when I talk about the dual of the Voroni Graph, I'm referring to the dual of this layout of the Voroni Graph.


What is the dual of the Voroni Graph? To answer that qualitatively, we're going to have to take sharp turn, click our heels, and talk about something that is, at first glance, completely different.


Suppose we have a set of points in the plane, and we want to triangulate it, or create a set of triangles, each with vertexes in the set of points we started with. Furthermore, we want to make sure that our triangulation has some special properties. For instance, we want make sure that none of our triangles overlap. We'd like them all to be reasonably shaped, and not too long and pointy. We'd also like them to fill as much of the plane as possible.


It's easy to verify that a triangulization doesn't overlap, but the other two conditions are less objective, and worse they sometimes contradict. Should we include a long triangle if there are no better options for filling space? To strike a compromise, we'll accept a triangle into our set if (and only if) no other points in out set lie within the triangle's circumcircle ( The circle that passes through all three vertices of the triangle ).

The set of all triangles formed form a set of points so the ate circumcircle of each triangle contains no extra points for the set is called the Delaunay Triangulation of the set. It (and it's generalizations to higher dimensions are) is a very important and interesting triangulation of the set, and hopefully we'll use it a lot going forward. In the mean time, however, I need to explain the relationship of the Delaunay Triangulation to the Voroni Graph.


We can construct a graph (with an associated layout) from the Delaunay Triangulation as follows: Each triangle becomes a node located at the center of the triangle's circumsphere (aka it's circumcenter), and two nodes are linked if their triangles share an edge. I also find it useful to imagine a node located at infinity, and add edges from nodes that have fewer than three connections to this imaginary node. I'm going to refer to this whole construction as the Delaunay Graph, though I haven't seen this anywhere else (To be honest, I haven't found much use for the Delaunay Graph yet, except as a conceptual tool for demonstrating how all this is related to the Voroni Graph).


Take a look at the conceptual sketch below (mostly to scale). As noted,  in this case, the Delaunay Graph and the Voroni Graph are duals. In fact, looking closer, the drawing of the Voroni Diagram and the Delaunay Graph share a common structure, as do the Delaunay Triangulation and the Voroni Graph.

Based of this, we might conjecture the following:

1. The Voroni Graph and Delaunay Graph are duals.
2. Every Triangle in the Voroni Graph is in the Delaunay Triangulation (and vice versa).

These are both very important ideas, and we'll be making heavy use of them (especially number 2) in future posts. But they are not completely true for Euclidian space, and it's important to understand when and why they can go wrong. For that, I'll introduce the following simple pathological example:

As you can see, the Voroni Graph for this set of points has four triangles as marked. Three of them complete the Delaunay Triangulation, but the fourth is NOT in the Delaunay Triangulation. Why does this happen (and can we expect it to happen often enough that we need to adjust for it)? My best answer, which I fully admit is a little handwavy, is that our statement about "Every Triangle in the Voroni Graph" is an inherently topological statement. It doesn't really take into account what space we're working in, and in this case, if we put these points through a stereographic projection and look a the result on a sphere, then yes, all four of these triangles are valid parts of the Delaunay triangulation.

I'd love to stop here, and say that therefore this is something we can neglect because it'll only occur at most once on a dataset, and our datasets should be large enough that this one spurious triangle should get covered up pretty fast. Unfortunately, there's also the perfectly valid example given below.

I don't have an answer for this one, and I don't really know that there is one. The outer triangle I can explain away with the same stereographic projection trick, but there's just no excuse for the one in the middle in two dimensions (Unless of course, you've got a better grasp on this than me, in which case, you should leave a comment!). Worse, this counterexample can be embedded in any otherwise well behaved set of points for an instant spurious triangle.

At the end of the day, however, I'm going to claim that this kind of thing doesn't seem to be very common. If I throw down a set of random points, I've haven't yet seen it come up of it's own accord. In the long run, I think the jury will be out until I've written a program that can make a few million large point sets and search for these sorts of things. And in that vein, we'll be discussing how to implement such a program next time.