Ninth International Conference on Parallel and Distributed Systems (ICPADS'02) A Parallel Divide-and-Conquer Scheme for Delaunay Triangulation Taiwan, ROC December 17-December 20 ISBN: 0-7695-1760-9
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 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.
Index Terms:
Unstructured mesh generation, Delaunay triangulation, Parallel algorithm.
Citation:
Min-Bin Chen, Tyng-Ruey Chuang, Jan-Jan Wu, "A Parallel Divide-and-Conquer Scheme for Delaunay Triangulation," icpads, pp.571, Ninth International Conference on Parallel and Distributed Systems (ICPADS'02), 2002 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb