Horizontal Expanding Method—A Quick Algorithm for Generating Delaunay Triangulation from Points in the Plane

Delaunay triangulation in the plane is a fundamental tool for building DEMs of triangulated irregular networks and generating Voronoi diagrams from points in the plane.There has been a lot of algorithms for generating Delaunay triangulation/ Of these algorithms,triangle-expanding method and point-interpolation method's average time complexity is O(n2),while Divide-and-Conquer algorithm and other divide-merge methods have the linear time complexity but the steps are more complex and their probability of occurring float-point computed error increased.The author of this article proposed a new algorithm as following:first,sorting the point set according to horizontal coordinates of each point,so the points are distributed from left to right spatially;then creating an initial triangulation based on the first 3 points to append the next point to triangulation each time and generate new triangles simultaneously;finally we get a triangulation created from the whole point set;the triangulation must be optimized by LOP method in order to turn it into Delaunay triangulation.The key originality of this algorithm is the triangulation method which results in high efficiency with the average time complexity of O(n) and the advantage of simplicity of this algorithm.