GREEDY BISECTION GENERATES OPTIMALLY ADAPTED TRIANGULATIONS

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 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 parallel to f - f(N)parallel to(Lp) <= CN-1 parallel to root det(d(2)f)parallel to(L tau) with 1/tau := 1/p + 1, which is known to be asymptotically optimal among all possible triangulations.