Computer Aided Engineering Design

MESH GENERATION 373

The advancing front method can be extended to three dimensions in that the front would comprise a
set of triangles at the surface of the solid to start with and interior points would be generated to create
almost regular tetrahedral elements.

A1.2.3 Delaunay Triangulation
The method is one of the most widely used as it yields efficient triangulation with relatively easy
implementation and provides better results for most applications. Delaunay triangulation is the geometric
dual of Voronoi tessellation also known as Theissen or Dirichlet tessellation in that one can be
derived from the other. For N points in a plane, Voronoi tessellation divides the domain into a set of
polygonal regions, the boundaries of which are perpendicular bisectors of the lines joining the nodes
(Figure A1.5 a). Each polygonal region contains only one of the N points.

Figure A1.4 Schematic of the advancing front method

Advancing

fronts

As per the Delaunay criterion, in a valid triangulation, the circumcircle of each triangle does not
contain any node of the mesh. By construction, each Voronoi vertex is the circumcenter of a Delaunay
triangle. Delaunay triangulation being the geometric dual of Voronoi tessellation, many methods
have been developed to arrive at the former using the latter, though many methods for direct triangulation
are also in use. A simple and widely used Watson’s algorithm for Delaunay triangulation is briefed

Figure A1.5 (a) Delaunary triangulation (solid) and Dirichlet tessellation (dashed) and

(b) Delaunay triangles with circumcircles

(a) (b)

Voronoi

vertex