A parallel divide-and-conquer scheme for Delaunay triangulation

This paper describes a parallel divide-and-conquer-algorithm for Delaunay triangulation. This algorithm finds the affected zone that cover the triangulations that may be modified during the merge of two sub-block triangulations. With the aid of the affected zone, communications between processors are reduced, the time complexity of divide-and-conquer remains O(n log n), and the affected zone can be found in O(n) time steps, where n is the number of points. The code was implemented with C, FORTRAN and MPI, so it was easy to port this program to other machines. Experimental results on IBM SP2 show that a parallel efficiency of 34%-96% for general distributions can be achieved on an 16-node distributed memory system.