Abstract: In this paper we are concerned with developing a practical parallel algorithm for Delaunay triangulation that works well on general distributions, particularly those that arise in Scientific Computation. Although there have been many theoretical algorithms for the problem, and some implementations based on bucketing that work well for uniform distributions, there has been little work on implementations for general distributions. We use the well known reduction of 2D Delaunay triangulation to 3D convex hull of points on a sphere or paraboloid. A variant of the Edelsbrunner and Shi 3D convex hull is used, but for the special case when the point set lies on either a sphere or a paraboloid. Our variant greatly reduces the constant costs from the 3D convex hull algorithm and seems to be a more promising for a practical implementation than other parallel approaches. We have run experiments on the algorithm using a variety of distributions that are motivated by various problems that use Delaunay triangulations. Our experiments show that for these distributions we are within a factor of approximately two in work from the best sequential algorithm.
@inproceedings{BlMiTa96,
Author="G. Blelloch and G.~L. Miller and D. Talmor",
Title="Developing a Practical Projection-Based Parallel
{Delaunay} Algorithm",
Booktitle="Proceedings ACM Symposium on Computational Geometry",
Year=1996,
month=may}