Computer Science Department
School of Computer Science, Carnegie Mellon University
Implementation and Evaluation of an Efficient
2D Parallel Delaunay Triangulation Algorithm
Jonathan C. Hardwick
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.