When and why Delaunay refinement algorithms work
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 degrees except "across" from small angles of the input. No angle of the output mesh is smaller than arctan [(sin theta*)/(2 - cos theta*)] where theta* is the minimum input angle. Moreover no angle of the mesh is larger than about 137 degrees, independent of small input angles. The adaptive variant is unnecessary when theta* is larger than 36.53 degrees, and thus Ruppert's Algorithm (with concentric shell splitting) can accept input with minimum angle as small as 36.53 degrees. An argument is made for why Ruppert's Algorithm can terminate when the minimum output angle is as large as 30 degrees.
ruppert's algorithm triangular mesh generation computational geometry