Title :
An efficient algorithm for constructing Delaunay triangulation
Author :
Jiang, Yu ; Liu, Yin-Tian ; Zhang, Fan
Author_Institution :
Intell. Inf. Process. Lab., Chengdu Uninversity of Inf. Technol., Chengdu, China
Abstract :
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).
Keywords :
mesh generation; optimisation; Deaunay condition; constructing Delaunay triangulation efficient algorithm; convex edges; triangles optimisation; Algorithm design and analysis; Data structures; Educational institutions; Information processing; Information technology; Laboratories; Mathematics; Optimization methods; Space technology; Testing; DEM; Delaunay triangulation; LOP optimizing; triangulated irregular networks;
Conference_Titel :
Information Management and Engineering (ICIME), 2010 The 2nd IEEE International Conference on
Conference_Location :
Chengdu
Print_ISBN :
978-1-4244-5263-7
Electronic_ISBN :
978-1-4244-5265-1
DOI :
10.1109/ICIME.2010.5478228
