NonObtuse Boundary Delaunay TriangulationsHitschfeld, Nancy and M. Cecilia RivaraProceedings, 6th International Meshing Roundtable, Sandia National Laboratories, pp.391, October 1997


Nancy Hitschfeld and M. Cecilia Rivara
Abstract The construction of the good quality (constrained) Delaunay triangulation consists of(a)The generation of any constrained Delaunay triangulation, and b) the use of an algorithm that improves the quality of the mesh so that the minimum angle is greater than or equal to 300. For the improvement of the mesh, we use an algorithm that uses a LEPPDelaunay improvement algorithm in interior triangles and a special boundary treatment over boundary triangles. The basic LEPPDelaunay improvement strategy uses the LongestEdge Propagation Path of the target triangles (to be either refined and/or improved in the mesh) in order to decide which is the best point to be inserted, to produce a goodquality distribution of points. This strategy is repeatedly used until the target triangle is destroyed. The special boundary treatment technique both avoids the insertion of undesirable points in the neighborhood of the boundary and contributes to a better point distribution. The postprocessing to eliminate boundary triangles (with largest angle smaller than or equal to 120 degrees considers three cases: (a) triangles with only boundary edge which is opposite to an obtuse angle, (b) triangles with two boundary edges and one of them opposite to an obtuse angle, and (c) triangles with three boundary edges. The case (a) is solved by inserting the midpoint at the boundary edge. Since the obtuse angle is smaller than 120', no diagonal interchange is necessary. For the case (b) and since the insertion of a point on the longestboundary edge keep the obtuse angle in the new triangle with two boundary edges, we propose to insert two points so that the new boundary triangle with two boundary edges is isosceles. A triangle with three boundary edges (case (c)) is a very rare case. Depending on the angles of the triangle, one or two isosceles triangles with two boundary edges are generated. The postprocessing strategy can be extended to handle interfaces. For obtuse triangles with one interface edge the slime strategy as for case (a) is applied. There is no need of diagonal interchange. For interface triangles with two or more interface edges adjacent to other triangles of the same type, we also propose the generation of isosceles triangles for the new triangles which keeps two interface edges. As a corollary, the final mesh without obtuse angles at the boundary and interfaces is a Delaunay triangulation also for the triangles lying at the boundary and interface.
Download Full Paper (PDF) Contact author(s) or publisher for availability and copyright information on above referenced article 