n-dimensional voronoi diagram - MathOverflow

n-dimensional voronoi diagram

2010-12-15T12:05:24Z

Hi, I need to compute the voronoi diagram of a set of points in R^n. I'm quite unschooled on the topic, could someone point me to the right references so that I can a) understand the theory behind it b) implement an actual algorithm to compute it

PS. Googling I found out I need to know about euclidean graphs, but I couldn't find any decent introduction to it. Pointers are appreciated!

Answer by Joseph O'Rourke for n-dimensional voronoi diagram

2010-12-15T13:05:16Z

Often Voronoi diagrams are constructed from their duals, Delaunay triangulations. The Delaunay triangulation of a point set in $d$ dimensions can be obtained from the convex hull of a lifting of the points into $d+1$ dimensions. This relationship is explained in many sources, including The Handbook of Discrete and Computational Geometry (Chapters 22, 23).

Implementing this on your own is quite a project, so you might first investigate what is available. Qhull performs the computations; see www.qhull.org. $d$-dimensional Delaunay triangulation computations are part of CGAL, specifically this module. You could use polymake to convert from the Delaunay triangulation to its corresponding Voronoi diagram. Finally, there are papers written on specific versions of your problem, for example: "An Explicit Solution for Computing the Euclidean $d$-dimensional Voronoi Diagram of Spheres in a Floating-Point Arithmetic," by Marina Gavrilova, 2003, link here.

(Incidentally, "Euclidean graphs" play a relatively minor role in this topic.)

Answer by Michael Hardy for n-dimensional voronoi diagram

2010-12-15T15:41:25Z

I think the "lifting of the points into $d+1$ dimensions" referred to in Joseph O'Rourke's answer means something like this: $(x_1,\dots,x_d) \mapsto (x_1,\dots,x_d,x_1^2+\cdots+x_d^2)$. Then the edges of the convex hull of those points in $d+1$ space connect the images of points that are connected in the Delaunay triangulation.

Answer by Grant Izmirlian for n-dimensional voronoi diagram

2010-12-15T19:15:56Z

R (a favorite open source, object oriented interactive statistical package) has what appears to be a suitably fast algorithm, but I've only used it in a problem with 20 some odd points or so.

As the others have mentioned above, the Voronoi tessellation or mosaic is computed using the (dual graph which is the) Delaunay triangulation. The R function 'veronoi.mosaic' in the package 'tripack' calls a FORTRAN routine. If its convenient enough to do it in R then just call the veronoi.mosaic function (details on getting R and getting the tripack package follow). Otherwise, if you'd rather just use the internal FORTRAN subroutine, you can figure out the meaning of the arguments by looking at the veronoi.mosaic function in R (at the point at which the FORTRAN subroutine 'veronoi' is called) and work backwards.

In any case, all of its open source and works like a charm.

getting R:

http://cran.r-project.org/

the tripack package

http://cran.r-project.org/web/packages/tripack/index.html

Enjoy!

Best Regards, Grant Izmirlian