► 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.