Quasi-Delaunay unstructured grid generation

we propose a Delaunay-like approach to quickly generate unstructured grid on two-dimensional domain. In this modified Delaunay approach, new point is inserted into the centroid of triangle at first and relocated to a proper position in the local triangulation consisting of triangles with their circumcircles containing the point. To speed up the triangulation process, we further set a limit on the construction of the local triangulation. By using proper algorithm, we show that our modified algorithm is more efficient than the traditional Delaunay methods with asymptotic computational complexity O(n) where n is number of the inserted points and, at the same time, generate a mesh with good quality. Numerical examples are shown to verify our arguments.