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

Jonathan C. Hardwick
CMU-CS-97-129, April 1997

176k gzip'd 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, 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.

@techreport{ Hardwick97TR,
	title = "Implementation and Evaluation of an Efficient {2D}
		Parallel {Delaunay} Triangulation Algorithm",
	author = "Jonathan~C. Hardwick",
	institution = "School of Computer Science, Carnegie Mellon University",
	number = "CMU-CS-97-129",
	year = 1997,
	month = apr
}