Parallel Delaunay Refinement:Algorithms And Analyses

Proceedings, 11th International Meshing Roundtable, Sandia National Laboratories, pp.205-218, September 15-18 2002

MESHING
RESEARCH
CORNER

11th International Meshing Roundtable
Ithaca, New York, USA
September 15-18, 2002

Daniel A. Spielman
Dept. of Mathematics, Massachusetts Institute of Technology,
spielman@math.mit.edu

Shang-Hua Teng
Dept. of Computer Science, Boston University and
Akamai Technologies Inc.,
steng@cs.bu.edu

Alper Ungor
Dept. of Computer Science, Duke University,
ungor@cs.duke.edu

Abstract
In this paper, we analyze the complexity of natural parallelizations of Delaunay renement methods for mesh gener- ation. The parallelizations employ a simple strategy: at each iteration, they choose a set of \independent" points to insert into the domain, and then update the Delaunay triangulation. We show that such a set of independent points can be constructed effeciently in parallel and that the number of iterations needed is O(log2(L=s)), where L is the diameter of the domain, and s is the smallest edge in the output mesh. In addition, we show that the insertion of each independent set of points can be realized sequentially by Ruppert's method in two dimensions and Shewchuk's in three dimensions. Therefore, our parallel Delaunay refinement methods provide the same element quality and mesh size guarantees as the sequential algorithms in both two and three dimensions. For quasi-uniform meshes, such as those produced by Chew's method, we show that the number of iterations can be reduced to O(log(L=s)). To the best of our knowledge, these are the rst provably polylog(L=s) parallel time Delaunay meshing algorithms that generate well-shaped meshes of size optimal to within a constant.

Download Full Paper (Postscript Format)