Premium
USING LONGEST‐SIDE BISECTION TECHNIQUES FOR THE AUTOMATIC REFINEMENT OF DELAUNAY TRIANGULATIONS
Author(s) -
RIVARA MARÍACECILIA,
INOSTROZA PATRICIO
Publication year - 1997
Publication title -
international journal for numerical methods in engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.421
H-Index - 168
eISSN - 1097-0207
pISSN - 0029-5981
DOI - 10.1002/(sici)1097-0207(19970228)40:4<581::aid-nme45>3.0.co;2-k
Subject(s) - delaunay triangulation , bisection method , constrained delaunay triangulation , chew's second algorithm , bowyer–watson algorithm , ruppert's algorithm , bisection , triangulation , algorithm , computer science , mathematics , geometry
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.