Optimal Delaunay Point Insertion

International Journal for Numerical Methods in Engineering, Wiley, Vol 39, pp.3407-3437, 1996

MESHING
RESEARCH
CORNER

H. Borouchaki and P. L. George: INRIA, Domaine de Voluceau, Rocquencourt, BP 105, 78153 Le Chesna,v Cedex. France
S. H. LO: Department of Civil and Structural Engineering, University of Hong Kong, Hong Kong

Summary
An efficient algorithm for Delaunay triangulation of a given set of points in d dimensions is presented. Various steps of the point insertion algorithm are reviewed and many acceleration procedures are implemented to speed up the triangulation process. New features include the search for a neighbouring point by a layering scheme, locating the containing simplex by a random walk, formulas of important geometrical quantities of a new simplex based on those of an old one, a novel approach in establishing the adjacency relationship using connection matrices. The resulting scheme seems to be one of the fastest triangulation algorithms known, which enables us to generate tetrahedra in R3 with a linear generation rate of 15 000 tetrahedra per second for randomly generated points on an HP 735 workstation.