Greedy bisection generates optimally adapted triangulations
Jean-Marie Mirebeau, Albert Cohen · Mathematics of Computation · 2011
We study the properties of a simple greedy algorithm for the generation of data-adapted anisotropic triangulations. Given a function f f , the algorithm produces nested triangulations T N \mathcal {T}_N and corresponding piecewise polynomial approximations f N f_N of f f . The refinement procedure picks the triangle which maximizes the local L p L^p approximation error, and bisects it in a direction which is chosen so to minimize this error at the next step. We study the approximation error in the L p L^p norm when the algorithm is applied to C 2 C^2 functions with piecewise linear approximations. We prove that as the algorithm progresses, the triangles tend to adopt an optimal aspect ratio which is dictated by the local hessian of f f . For convex functions, we also prove that the adaptive triangulations satisfy the convergence bound ‖ f − f N ‖ L p ≤ C N − 1 ‖ det ( d 2 f ) ‖ L τ \|f-f_N\|_{L^p} \leq CN^{-1}\|\sqrt {\det (d^2f)}\|_{L^\tau } with 1 τ