
Title  Piecewise Optimal Triangulation for the Approximation of Scattered Data in the Plane
(In Proceedings) 
in  Computer Aided Design 
Author(s) 
Martin Bertram, James C. Barnes, Bernd Hamann, Ken Joy, Helmut Pottmann, Dilinur Wushour 
Keyword(s)  triangulation, datadependent tirangulation, approximation, hierarchical approximation, quadratic polynomials, clustering 
Year 
2000

Volume  17 
Number  8 
Publisher  Elsevier 
Pages  767787 
Download  
BibTeX  
Abstract 
We present an efficient algorithm to obtain a triangulated graph surface for scattered points (x_{i} y_{i})^{T}, i= 1...n, with assoiciated function values ƒ_{i}. The maximal distance between the triangulated graph surface and the function values is measured in zdirection (z= ƒ (x, y) and lies within a userdefined tolerance. The number of triangles is minimized locally by adapting their shape to different seconddegree least squares approximations of the underlying data. The method consists of three major steps: (i) subdividing the given discrete data set into clusters such that each cluster can be approximated by a quadratic polynomial within a prescribed tolerance; (ii) optimally triangulating the graph surface of each quadratic polynomial; and (iii) "stitching" the triangulations of all graph surfaces together. We also discuss modifications of the algorithm that are necessary to deal with discrete data points, without connectivity information, originating from a general twomanifold surface, i.e., a surface in threedimensional space that is not necessarily a graph surface.
