An efficient algorithm for constructing Delaunay triangulation
Yu Jiang, Yintian Liu, Fan Zhang · 2010
An algorithm for fast constructing Delaunay triangulations was proposed. In iterations, this algorithm is to select the leftmost one point lying right some convex edges from set of points. The point and those convex edges construct new triangles, and add them to Delaunay triangulations. At same time, when new triangles do not meet Deaunay condition, optimize triangles based on LOP method, which is implemented in non-recursive way, and only needs computing and flipping. The average time complexity of the algorithm is analyzed, and it is O(n).