Proceedings ACM Symposium on Computational Geometry, May 1996.

**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}