When and why Ruppert's algorithm works

Proceedings, 12th International Meshing Roundtable, Sandia National Laboratories, pp.91-102, Sept. 2003

MESHING
RESEARCH
CORNER

12th International Meshing Roundtable
September 14-17, 2003
Santa Fe, New Mexico, U.S.A.

Carnegie Mellon University, Pittsburgh, PA 15213 U.S.A.
glmiller@cs.cmu.edu; spav@andrew.cmu.edu; noelw@andrew.cmu.edu

Abstract
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 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 137.1 degrees. 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.

Download Full Paper (PDF Format)