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

fYear

2010

fDate

16-18 April 2010

Firstpage

600

Lastpage

63

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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/ICIME.2010.5478228

Filename

5478228