2010 · 17 citations · 4 references
ComputingComputer ScienceAlgorithmsComputational GeometryTheory Of ComputationDelaunay TriangulationsGeometric OptimizationGeometry ProcessingDelaunay Triangulation AlgorithmsTriangulation AlgorithmsTriangulations
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).
4