## Introduction

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 `ArrayList`

s and `HashSet`

s.

## The Implementation

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 `double`

s 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 `double`

s.

A `VoronoiGraph`

is a class that only contains a `HashSet`

of vertices (as 2D vectors) and a `HashSet`

of `VoronoiEdge`

s - 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.

## Usage

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.