Given a set of two dimensional vectors (or data points), a Voronoi graph is a separation of those points into compartments where all points inside one compartment are closer to the contained data point than to any other data point. I won't give any demonstration here, but if you want to know more about Voronoi graphs, check out this.
The applications of Voronoi graphs are quite broad. Very useful for a lot of optimization problems (in most cases, the Delaunay Triangulation which can be easily derived from a Vononoi graph is used there), it ranges to computing topological maps from bitmaps.
[This is an article for freaks. After a rather painful experience writing the thing I hope it will benefit everyone who is looking for this algorithm in a civilized language (or simply does not want to use Fortune's original C implementation).]
In 1987, Steve Fortune described an algorithm to compute such a graph by using a sweep line in combination with a binary tree. A PowerPoint explanation of the algorithm (the one I used to implement it) can be found here. Note that I did not use the linked data structure to represent a graph - I think that is an unnecessary difficulty in the age of
Data points are represented by my own
Vector class. It can do much more than needed here (but there was no reason to strip it before bringing it) but I won't explain it here. The most important fact is that although working with
doubles the Vector class automatically rounds values to 10 digits (or whatever is set in the
Vector.Precision field). Yes, sadly, this is very important if you want to sort of compare
VoronoiGraph is a class that only contains a
HashSet of vertices (as 2D vectors) and a
VoronoiEdges - each with references to the left and right data point and (of course) the two vertices that bound the edge. If the edge is (partially or completely) unbounded, the vector
Fortune.VVUnknown is used.
BinaryPriorityQueue is used for the sweep line event queue.
The algorithm itself (
Fortune.ComputeVoronoiGraph(IEnumerable)) takes any
IEnumerable containing only two dimensional vectors. It will return a
VoronoiGraph. The algorithm's complexity is O(n ld(n)) with a factor of about 10 microseconds on my machine (2GHz).
I did my diploma in Dresden and Sydney where I dealt with algorithms, agents and other cool AI stuff. Now I moved to Frankfurt to work on my PhD dealing with software structures for artificial intelligence systems. If I can, I do things in C# and ASP.NET, but if I have to, my C++, Java and SQL are not that bad.
Long Live .NET.