Implementation and Evaluation of an Efficient 2D Parallel Delaunay Triangulation Algorithm

Proceedings of the 9th Annual ACM Symposium on Parallel Algorithms and Architectures, ACM, Vol 15, June 1997

MESHING
RESEARCH
CORNER

School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213

Abstract
This paper describes the derivation of an empirically efficient parallel two- dimensional Delaunay triangulation program from a theoretically efficient CREW PRAM algorithm. Compared to previous work, the resulting implementation is not limited to datasets with a uniform distribution of points, achieves significantly better speedups over good serial code, and is widely portable due to its use of MPI as a communication mechanism. Results are presented for a loosely-coupled cluster of workstations, two distributed-memory multicomputers, and a shared-memory multiprocessor. The Machiavelli toolkit used to transform the nested data parallelism inherent in the divide-andconquer algorithm into achievable task and data parallelism is also described and compared to previous techniques.

Download Paper from authors site