WHEN AND WHY DELAUNAY REFINEMENT ALGORITHMS WORK
Gary Lee Miller, Steven E. Pav, Noel J. Walkington · International Journal of Computational Geometry & Applications · 2005
An "adaptive" variant of Ruppert's Algorithm for producing quality triangular planar meshes is introduced. The algorithm terminates for arbitrary Planar Straight Line Graph (PSLG) input. The algorithm outputs a Delaunay mesh where no triangle has minimum angle smaller than about 26.45° except "across" from small angles of the input. No angle of the output mesh is smaller than arctan [(sin θ*)/(2-cos θ*)] where θ* is the minimum input angle. Moreover no angle of the mesh is larger than about 137°, independent of small input angles. The adaptive variant is unnecessary when θ* is larger than 36.53°, and thus Ruppert's Algorithm (with concentric shell splitting) can accept input with minimum angle as small as 36.53°. An argument is made for why Ruppert's Algorithm can terminate when the minimum output angle is as large as 30°.