# Fastest Delaunay triangulation libraries for sets of 3D points

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?

-
 Have you tried the implementations in the CGAL and TRIANGLE softwares? Both include $O(nlog(n))$ algorithms, which are (theoretically) the fastest available (albeit not in parallel). – Paul♦ Apr 23 '12 at 17:58 Jonathan Shewchuk also has a streaming version for 2D that can handle ridiculously large datasets if you can add some extra data to your stream. What are you using this for? – Victor Liu Apr 24 '12 at 10:27

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.

-

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.

-