Delaunay triangulation from convex hull

Question

I need to write some codes on computational geometry and parallelize them using openMP.So far, I have finished convex hull and closest pair of points.I need to write the delaunay triangulation divide and conquer code.But I dont have much time.I read somewhere that delaunay triangulation can be easily implemented if the convex hull can be calculated.So if anyone can provide me the serial code for DT or atleast let me know how i could generate the delaunay triangulation from convex hull, i could write the code and parallelize it as soon as possible.

Answer 1

I read somewhere that delaunay triangulation can be easily implemented if the convex hull can be calculated.

This is true, but the precise statement is that the 2D Delaunay triangulation can be easily constructed if a 3D convex hull implementation is available. Knowing the 2D hull does not help much with constructing the Delaunay triangulation (DT), besides giving you a few edges of the DT (each hull edge is an edge of the DT).

Assuming you have not implemented the 3D hull (which is quite tricky), then you need to attack the Delaunay triangulation separately.

Answer 2

QHull is pretty much the standard library many people use: http://www.qhull.org/html/qhull.htm Perhaps you can use it as a reference implementation, if you really want to reimplement this.