Implementation and Evaluation of an Efficient Parallel Delaunay Triangulation Algorithm

Jonathan C. Hardwick.
Proceedings of the 9th ACM Symposium on Parallel Algorithms and Architectures, June 1997.

162k compressed postscript

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, a distributed-memory multicomputer, 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.

@inproceedings{ hardwick97implementation,
    author = "Jonathan C. Hardwick",
    title = "Implementation and Evaluation of an Efficient Parallel Delaunay Triangulation Algorithm",
    booktitle = "Proceedings of the 9th {ACM} Symposium on Parallel Algorithms and Architectures",
    pages = "239-248",
    year = "1997",
    month = "June",
    url = "citeseer.nj.nec.com/hardwick97implementation.html" }

A later version of this paper appeared as CMU-CS-97-129.