Piecewise optimal triangulation for the approximation of scattered data in the plane Original Research Article

We present an efficient algorithm to obtain a triangulated graph surface for scattered points (xi yi)T, i=1,…,n, with associated function values fi. The maximal distance between the triangulated graph surface and the function values is measured in z-direction (z=f(x,y)) and lies within a user-defined tolerance. The number of triangles is minimized locally by adapting their shapes to different second-degree least squares approximations of the underlying data. The method consists of three major steps: