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!
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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]
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]"