3
$\begingroup$

I'm a software engineer and have been asked to research a Voronoi implementation in four dimensions. I'm not asking for "teh codez" but am interested in approachable tutorials on Voronoi decomposition and/or implementations in any dimension. Any help here would be greatly appreciated!

2 Answers 2

6

The standard survey is Aurenhammer and Klein. Have you looked at that?

[This would be a comment, but I don't have enough rep on this site yet]

4

Even though you didn't ask for 'teh codez' :), qvoronoi is a pretty good implementation of Voronoi diagrams for low dimensions (i.e 4). It actually computes the Delaunay triangulation, which in turn is constructed by a convex hull algorithm (qhull) one dimension higher.

The convex hull algorithm itself is a combination of "the 2-d Quickhull algorithm with the n-d beneath-beyond algorithm [c.f., Preparata & Shamos '85]"