Fastest Delaunay triangulation libraries for sets of 3D points

Question

Which is the fastest library for performing delaunay triangulation of sets with millions if 3D points? Are there also GPU versions available? From the other side, having the voronoi tessellation of the same set of points, would help (in terms of performance) for getting the delaunay triangulation?

Answer 1

For computing three-dimensional Delaunay triangulations (tetrahedralizations, really), TetGen is a commonly used library.

For your convenience, here's a little benchmark on how long it takes to compute the terehedralization of a number of random points from the unit cube. For 100,000 points it takes 4.5 seconds on an old Pentium M.

^{(This was done with Mathematica's TetGen interface. I don't know how much overhead it introduces.)}

Regarding your other question: if you already have the Voronoi tessellation, then getting the Delaunay triangulation is a relatively simple transformation.

Answer 2

If you already have the voronoi diagram of a set of points, then computing the Delaunay triangulation will only take you O(n). Equivalently, given a voronoi point, you can obtain its Delaunay triangle in O(1). They are dual so try exploiting this situation whenever is possible.