Cost analysis of the longest-side (triangle bisection) refinement algorithm for triangulations

摘要: The triangulation refinement problem, as formulated in the adaptive finite element setting (also useful rendering of complex scenes), is discussed. This can be follows: given a valid, non-degenerate polygonal region, construct locally refined triangulation, with triangles prescribed size regionR, and such that smallest (or largest) angle bounded. To cope this longest-side algorithms guarantee construction good quality irregular triangulations. due part to their natural propagation strategy farther than (refinement) area interestR. In paper we prove that, asymptotically, numberN points inserted inR obtain size, optimal. Furthermore, spite unavoidable outside time cost algorithm linear inN, independent triangulation. Specifically, number outsideR orderO(n log 2 n) whereN=O(n2). We latter result for circular rectangular regions, which allows us conclude true general convex regions. also include empirical evidence, both two three dimensions, complete agreement theory, even small values ofN.