Delaunay triangulation of non-uniform point distributions by means of multi-grid insertion

In the light of the simplicity and the linearity of regular grid insertion, a multi-grid insertion scheme is proposed for the Delaunay triangulation of uniform and non-uniform point distributions by recursive application of the regular grid insertion to an arbitrary subset of the original point set. The fundamentals and difficulties of Delaunay triangulation of highly non-uniformly distributed points by the insertion method are discussed. Current strategies and methods of point insertions for non-uniformly distributed points are reviewed. An enhanced kd-tree insertion scheme with specified number of points in a cell and its natural sequence of insertion are presented.The regular grid insertion, the enhanced kd-tree insertion and the multi-grid insertion have been thoroughly tested with benchmark non-uniform distributions of 1–100 million points. It is found that the kd-tree insertion is very sensitive to the triangulation of non-uniform point distributions with a large amount of conflicting elongated triangles. Multi-grid insertion is the most stable and efficient for all the uniform and non-uniform point distributions tested.

► Regular grid insertion to achieve linear complexity in Delaunay triangulation.
► An enhanced kd-tree insertion scheme for non-uniformly distributed points.
► Multi-grid insertion scheme as a recursive application of regular grid insertion.
► Benchmark non-uniform point distributions from 1 million to 100 million points.
► The multi-grid insertion scheme is robust and the most efficient.