Optimal delaunay point insertion

Abstract

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 ℝ3 with a linear generation rate of 15000 tetrahedra per second for randomly generated points on an HP 735 workstation.