Computational Complexity of the Advancing Front Triangulation

Engineering with Computers, Springer-Verlag, Vol 12, pp.16-22, 1996

MESHING
RESEARCH
CORNER

Department of Structural Mechanics, Czech Technical University in Prague, Thakurova 7, 16608 Prague, Czech Republic

Abstract
An attempt to reduce the computational complexity of the advancing front triangulation is described. The method is first decomposed into subtasks, and the computational complexity is investigated separately for them. It is shown that a major subtask, namely the geometric compatibility (mesh correctness) checks, can be carried out with linear growth rate. The applied techniques include modified advancing front management, and a localization device in the form of a regular grid (stored as a hypermatrix). The other subtask (access to mesh control function) could not be made of linear computational complexity for all modes of mesh control (ad hoc and adaptive). While the ad hoc gradation control yields an algorithm with ideal overall computational complexity the adaptive gradation control gives still a suboptimal complexity (of order O(N log N)).