Delaunay triangulation of arbitrarily shaped planar domains (Q1183535)

An algorithm is developed for automatically discretizing (triangulating, the procedure is denoted domain Delaunay triangulation, DDT) arbitrarily shaped (i.e. convex or nonconvex, manifold or nonmanifold) multiply- connected 2-D domains. New nodes are inserted on the boundaries of the domain, on the basis of a necessary and sufficient condition for an edge to be a Delaunay edge and thus the number of inserted new nodes is always less or equal to the one resulting from existing algorithms. Operations of point (or standard) Delaunay triangulation and refined edges are involved in the procedure. The DDT algorithm is compared with the ``Empty-Disk'' algorithm by \textit{J. D. Boissonnat} [Graphics and Image Processing 44, 1-29 (1988)] and with the ``Stitching'' algorithm by \textit{W. J. Schroeder} et al. [Int. J. Numer. Methods Eng. 26, No. 11, 2503-2515 (1988; Zbl 0662.73052)]. Applications of the DDT algorithm are suggested for automatic meshing of solid models, semiautomatic finite-element meshing, surface interpolation, and shape characterization.