
Title  On a Construction of a Hierarchy of Best Linear Spline Approximations using Repeated Bisection
(Article) 
in  IEEE Transactions on Visualization and Computer Graphics 
Author(s) 
Bernd Hamann, Benjamin Jordan, David F. Wiley 
Keyword(s)  approximation, bisection, best approximation, grid generation, hierarchical representation, linear spline, multiresolution method, scattered data, spline, triangulation, unstructured grid, visualization 
Year 
1999

Download  
BibTeX  
Abstract 
We present a method for the construction of hierarchies of singlevalued functions in one, two, and three variables. The input to our method is a coarse decomposition of the compact domain of a function in the form of an interval (univariate case), triangles (bivariate case), or tetrahedra (trivariate case). We compute the best linear spline approximations, understood in an integral least squares sense, for functions defined over such triangulations and refine triangulations using repeated bisection. This requires the identification of the interval (triangle, tetrahedron) with largest error and splitting it into two intervals (triangles, tetrahedra). Each bisection step requires the recomputation of all spline coefficients due to the global nature of the best approximation problem. Nevertheless, this can be done efficiently by bisecting multiple intervals (triangles, tetrahedra) in one step and by reducing the bandwidths of the matrices resulting from the normal equations.
