Greedy bisection generates optimally adapted triangulations

Abstract:

We study the properties of a simple greedy algorithm for the generation of data-adapted anisotropic triangulations. Given a function $f$, the algorithm produces nested triangulations $\mathcal {T}_N$ and corresponding piecewise polynomial approximations $f_N$ of $f$. The refinement procedure picks the triangle which maximizes the local $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$ norm when the algorithm is applied to $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$. For convex functions, we also prove that the adaptive triangulations satisfy the convergence bound $\|f-f_N\|_{L^p} \leq CN^{-1}\|\sqrt {\det (d^2f)}\|_{L^\tau }$ with $\frac 1 \tau :=\frac 1 p + 1$, which is known to be asymptotically optimal among all possible triangulations.