Introuction:
The Delaunay Triangulation (DT) is fundamental to computational
geometry and arises naturally in many domains. Sequential algorithms
for DT have been studied from both a theoretical and practical point of
view. Fortune gives performance analysis of many of these algorithms
[For92]. Parallel algorithms for this problem have also been
designed. There are several theoretically optimal parallel algorithms,
but they seem to have large constants in the work
they perform and are also complicated to code.
Thus, the parallel implementation we are aware of are simpler
algorithms and efficient only for special data sets. In
particular, they work best with uniformly distributed data sets,
[Su][TSBP93].
This is an animation of a new parallel DT algorithm. Our algorithm is based on the ``marriage before conquest''(pre-divide-and-conquer) paradigm. It has similarities to the 3-D convex hull algorithm of Edelsbrunner and Shi [ES91] and graph separator approach of Miller, Talmor and, Teng [MTT94]. We take advantage of the fact that there are parallel 2-D convex hull algorithms such as ``quick hull'', another pre-divide-and-conquer parallel algorithm, that are efficient in practice.
A Delaunay triangulation of point set P is a triangulation such that the circle defined by each triangle contains no points from P in its interior. The Delaunay Triangulation can be reduced to a 3d-convex hull, using the lifting transformation, which vertically maps a point p=(x,y) to the point p' = (x,y,||p||^2), which lies on the paraboloid z = x^2+y^2. The edges of the Delaunay triangulation of P are then a vertical projection of the convex hull edges of P'.
We begin the algorithm with P, and its 2-d convex hull edges. At each iteration, a cut path composed of Delaunay edges is used to separate the problem into two subproblems. Computing the cut is done in the following way: We show that given any line L in the plane, we can compute the border C of a cut of the Delaunay Diagram, such that Delaunay triangles whose circumcenter lies to the left(right) of L lie left(right) to C. The cut-border C is computed by using the lifting transformation to map P onto the paraboloid whose lowest point lies on the line L, projecting P' onto the vertical plane passing through L, and computing the 2D convex hull of the projected points.
The main computational steps the algorithm performs in each iterations are finding a median line and dividing the point set, 2-d convex hull to find the new border, and merging the new border with the old.
Preliminary experiments with the algorithm indicate O(n log n) work. Our data sets included the following random distributions:
We observed only a constant factor difference in the run time depending on the distribution. The second two distributions are known not to work efficiently with other algorithms[Su][TSBP93].