AnO(N) algorithm to automatically generate geometric triangulations satisfying the Delaunay circumsphere criteria

This paper presents an algorithm for the generation of Delaunay triangulations for general nonmanifold geometric models. Octree concepts are used for point placement and providing the linear, with respect to the number of elements, growth rate of the algorithm. Compatibility and classification procedures are used in conjunction with point injection procedures to ensure that the final Delaunay triangulation is a geometric triangulation of the domain of interest.