12th International Meshing Roundtable
September 1417, 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)
Contact author(s) or publisher for availability and copyright information on above referenced article
