carrier image

Parallel Delaunay Refinement:Algorithms And Analyses

Spielman, Daniel A., Shang-Hua Teng, Alper Ungor

Proceedings, 11th International Meshing Roundtable, Springer-Verlag, pp.193-204, September 15-18 2002


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

Daniel A. Spielman
Dept. of Mathematics, Massachusetts Institute of Technology,

Shang-Hua Teng
Dept. of Computer Science, Boston University and
Akamai Technologies Inc.,

Alper Ungor
Dept. of Computer Science, Duke University,

In two dimensions, a constrained Delaunay triangulation (CDT) respects a set of segments that constrain the edges of the triangulation, while still maintaining most of the favorable properties of ordinary Delaunay triangulations (such as maximizing the minimum angle). CDTs solve the problem of enforcing boundary conformityóensuring that triangulation edges cover the boundaries (both interior and exterior) of the domain being modeled. This paper discusses the three-dimensional analogue, constrained Delaunay tetrahedralizations (also called CDTs), and their advantages in mesh generation. CDTs maintain most of the favorable properties of ordinary Delaunay tetrahedralizations, but they are more difficult to work with, because some sets of constraining segments and facets simply do not have CDTs. However, boundary conformity can always be enforced by judicious insertion of additional vertices, combined with CDTs. This approach has three advantages over other methods for boundary recovery: it usually requires fewer additional vertices to be inserted, it yields provably good bounds on edge lengths (i.e. edges are not made unnecessarily short), and it interacts well with provably good Delaunay refinement methods for tetrahedral mesh generation.

Download Full Paper (PDF Format)

Contact author(s) or publisher for availability and copyright information on above referenced article