4/10/12

Voroni Diagrams and Graphs II: Some Applications of the Voroni Graph.

In this post, I'll further discuss the concept of the Voroni graph we talked about last time, and talk about some uses. We'll see more uses in the next post, where I'll talk a bit about a related graph.

Supposing we know the Voroni Graph of a set of points, what can we do with it?

First, we can use it to check if a point p is in the Voroni cell of some point in our set q. If we find all the neighbors of q ( points that have an edge to q in the Voroni Graph ) we only have to check to make sure that p is closer to q than any of these points, since we already know that these neighbors alone are sufficient to define the cell of q.

Let's briefly look at how much of an improvement this is over a normal check. Let's assume we have a set of n randomly distributed points, and n is very large (AKA we can neglect the effects of the outermost border of the points, and we're not going to get anything unusual in our graph).

If we have to check each point to see if p is closest to q, then we'll take O(n) time. This isn't bad, but if we assume we have access to the Voroni graph, we can do much better.

We need to find how many neighbors a typical Voroni diagram has.We know that the Voroni graph is planar, so it will obey Euler's formula ( V − E + F = 2 ). If the points are fairly random, then almost all of the "faces" of the graph will be triangles ( A non triangular face, we'll see later, implies that at least four of the points lie on a single circle, which is in general not true. ). Because of this F = 2E / 3 ( each triangle is bounded by three edges, and each edge divides two triangles ).

V - E + (2/3) E = 2
V - 2 = (1/3) E
E/V = 3 - 6 / V
2E/V = 6 - 12 / V

The quantity 2E/V represents the average number of neighbors of each vertex (we double the number of edges so that both ends can count it). Thus, as the number of vertices becomes large, each vertex will have on average only 6 neighbors. Thus, if we can use the Voroni Graph, we can check our point in only O(1) time!

It's worth noting of course, that this isn't quite as good as it seems. After all, we still have to compute the Voroni Graph, and we'll need to store it in such a way as to allow ourselves to look up a given vertex quickly. Still, it's an achievement, and it lets us know that if we're going to be checking lots of points, we'd be better off investing our time in making the Voroni graph rather than brute forcing the problem.

Even better, because p is in the cell of q if and only if it is closer to q than q's neighbors, it is also painless to find out which point is closest to p. We simply pick a starting point q1, and check if that point is closest to p. If it is not, we call the neighbor of q1 q2, and check if it is closest. This continues until we find that p is closest to qn relative to its neighbors Because of the nice properties of the Voroni graph, we can say that qn will be the point in our point set which is closest to p. In other words, having the Voroni graph lets us do a greedy search to find the Voroni cell to which a point belongs.

I would love to analyse the run-time of this particular algorithm, given a large set of points and a randomly chosen starting point, but I must confess I am not clever enough to put down any of my thoughts on paper at this point. I'll continue to think on it, but my money is on O( n1/2 ) for 2D ( and more generally O( n1/d ) for dimension d ). I think this is how the average euclidean distance between two randomly selected points scales as the number of points increases.

In any case, it is a great improvement over the naive approach, which would require us to check the distance to every point, and thus would have O( n ) run-time.

That's it for this post. I've got two more queued up and ready to go as soon as I have time to edit them and add figures, so expect more on this topic soon.