USING LONGEST-SIDE BISECTION TECHNIQUES FOR THE AUTOMATIC REFINEMENT OF DELAUNAY TRIANGULATIONS
María‐Cecilia Rivara, Patricio Inostroza · International Journal for Numerical Methods in Engineering · 1997
In this paper we discuss, study and compare two linear algorithms for the triangulation refinement problem: the known longest-side (triangle bisection) refinement algorithm, as well as a new algorithm that uses longest side bisection techniques for refining Delaunay triangulations. We show that the automatic point insertion criterion, taken from the fractal property of optimal (linear) longest-side bisection algorithms, assures the construction of good quality Delaunay triangulations in linear time. Numerical evidence, showing that the practical behaviour of the new algorithm is in complete agreement with the theory, is included. © 1997 by John Wiley & Sons, Ltd.