Coping with degeneracy in the computation of Dirichlet Tessellations

Abstract

A modification to the Dirichlet tessellation algorithm of Green and Sibson {1} is presented which deals effectively with degenerate and near-degenerate vertices and allows the construction of a consistent Delaunay triangulation for all sets of data. The modified algorithm produces contiguity lists which facilitate the computation of triangular finite element meshes quickly and efficiently and also allows points to be delet ed from the tessellation. The modification consists of a pair of rules which prevent the recording of degene rate vertices in the contiguity t able, and ensures that the subsequent triangulation is not ambiguous. The arbitrary triangular grid that is constructed between the actual data points can easily be used to compute two-dimensional contour diagrams, without the need for interpolation from the data points to the nodes of a rectangular grid system. The modified algorithms can also be used to compute a triangulated finite element mesh from the nodes of a rectangular grid system.