Computer Science Department
School of Computer Science, Carnegie Mellon University


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

Jonathan C. Hardwick

April 1997

An earlier version of this paper appears in Proceedings of the 9th Annual ACM Symposium on Parallel Algorithms and Architectures, June 1997.

Keywords: Two-dimensional Delaunay triangulation, parallel algorithm, divide-and-conquer, nested data parallel, Machiavelli, MPI

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-and-conquer algorithm into achievable task and data parallelism is also described and compared to previous techniques. An earlier version of this paper will appear in SPAA'97. 21 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by