Given a set S of data points on a surface F whose equation is z = f(x,y), we would like to triangulate the convex hull of the projection of F on the xy-plane. This triangulation determines a linear approximation of F whose quality is given by a measure of the approximation error. It has been recently proved that the Delaunay triangulation is optimal with respect to Lp-norm criteria, when used for approximating convex quadratic functions. But, little research has been carried out for non convex surfaces. This work studies the approximation, with respect to L1- and L2-norms, of a non convex surface by using a triangulation. We consider a simple case: the hyperbolic paraboloid z = x2 − y2. A construction is given for finding the separation curves of a triangle ∆, the curves limiting the planar zones where ∆ will be kept in a locally optimal triangulation of the hyperbolic paraboloid. Triangu- lation algorithms that use several heuristics based on the separation curves are amply tested and are shown to be better than the Delaunay triangulation. A comparison with globally optimal triangulations which are obtained by means of exponential programs shows that these algorithms finally give "good" trian- gulations. Our research proves that such a process can be easily extended to general quadratic functions z = αx2 + βy2 + γxy + δ1x + δ2y + δ3.
