  In this paper we provide the exact asymptotics of the optimal weighted
$L_p$-error, $0<p< \infty$, of linear spline interpolation of $C^2$ functions
with positive Hessian. The full description of the behavior of the optimal
error leads to the algorithm for construction of an asymptotically optimal
sequence of triangulations. In addition, we compute the minimum of the
$L_p$-error of linear interpolation of the function $x^2+y^2$ over all
triangles of unit area for all $0<p<\infty$. This provides the exact constant
in the asymptotics of the optimal error.

Numerical Analysis