Abstract: Given the enormous scale and diverse distribution of 2D point cloud data, a multi-grid combined with Hilbert curve insertion algorithm is proposed for improving the efficiency of Delaunay Triangulation. First of all, the division problem caused by regular grid insertion scheme for non-uniform distributed point set can be resolved by the multi-grid one. Then, a large amount of conflicting elongated triangles, which have to be created and deleted many times, can be avoided by adding control points and adopting Hilbert curve traversing grids. Lastly, searching steps for positioning inserting point can be reduced by adjusting the Hilbert curve in adjacent grids for the avoided “jumping” phenomenon. The experimental results show that the efficiency of Delaunay triangulation by multi-grid combined with Hilbert curve insertion algorithm can be improved significantly for both uniform and non-uniform distributed point cloud data compared with CGAL, regular grid insertion and multi-grid insertion algorithm.