Qhull solution

Hmmm... it turned out that the construction of Voronoi diagrams is far from trivial. There are some serious papers out there, and they involved quite a bit of mathematics, to put it mildly.

I started to study the 2d methods first.

The sweep method (java required for demo) seemed so not elegant to me. "Wave front", come on, what's that? :-) There must be a better way.

I found the divide-and-conquer approach, presented by Shamos and Hoey, much more elegant. It can be easily attacked with the object-oriented programming language.

But after some hours of intensive work some concernes began to arise. The algorithm was pretty complex, but I was still in 2d. What would happen in 3d? The complexity would go over the roof. After all, the Voronoi construction itself is not the topic of my research; it's merely a tool and I should spend as little time as possible for it.

I stopped the work with the divide-and-conquer construction of Voronoi and headed for the web again; let's find some more info about 3d Voronoi construction.

My fears that 3d Voronoi construciton is far from trivial were confirmed, when I discovered that two first-class mathematical tools, Mathematica and Mathlab, both use external library Qhull for Voronoi (and related) computations.

Qhull is a powerful software put together by nice people who seemingly allow us to use it freely. It can do convex-hull, Voronoi diagrams and Delaunay triangualtion (which is the dual of Voronoi) in not only 2d and 3d, but even in higher dimensions, at least up to 8d; so there was really no point in competing with it :-)

After a few hours crunching numbers and fighting with academic-style documentation, almost all of my Voronoi computation problems were solved. As a bonus, it turned out that Qhull was lightning fast as well. Happy ending!