Parallel delaunay triangulation

Question

I am trying to parallelize the Guibas Stolfi delaunay triangulation using openmp.

There are two things to parallelize here- the mergesort(),which i did and the divide() where I am stuck. I have tried all possible approaches but in vain.

The approach followed(divide n conquer) in divide() is same as that of mergesort(),but applying the same parallelization technique(omp sections) works only for mergesort.

I tried the parallelization technique shown here,but even that doesn't work. I read about nested parallelism somewhere but i am not sure how to implement it. Can anybody explain how divide and conquer algorithms are parallelized?

CODE:Called mergesort twice in main function and applied sections construct.Doing same for divide function doesn't work

#pragma omp parallel
{
#pragma omp sections nowait
{
#pragma omp section
{
merge_sort(p_sorted, p_temp, 0, n/2);
}
#pragma omp section
{
merge_sort(p_sorted, p_temp, (n/2)+1, n-1);
}
}
}

Answer 1

I was successful in parallelizing using the CreateThread calls in Windows, the trick is to divide the points into 2^n buffers, process each buffer in a separate thread and then merge adjacent edges, successively, until one final merge.

I have a demonstation program to create random data and triangulate and display the results (for smaller cases). It doesn't look like this site lets me download the .zip I have of the program and display tool. If you can suggest an upload site or provide an email I'll send it to you.