Implementation and evaluation of an efficient parallel Delaunay triangulation algorithm
Jonathan C. Hardwick · 1997
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 dataaets with a uniform dktribution 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 d~t ributed-memory mult icomputer, and a shared-memory multiprocessor.The MachL avelli 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. Outer Delaunay Triangulation