Title :
On a construction of a hierarchy of best linear spline approximations using repeated bisection
Author :
Hamann, Bernd ; Jordan, Benjamin W. ; Wiley, David F.
Author_Institution :
Center for Image Process. & Integrated Comput., California Univ., Davis, CA, USA
Abstract :
We present a method for the construction of hierarchies of single-valued 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 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
Keywords :
computational geometry; data visualisation; function approximation; least squares approximations; matrix algebra; splines (mathematics); data visualization; hierarchy construction; integral least squares; interval; linear spline approximations; matrices; multiresolution method; repeated bisection; single-valued functions; tetrahedra; triangles; Bandwidth; Data visualization; Equations; Least squares approximation; Linear approximation; Mesh generation; Scattering; Sparse matrices; Spline; Tellurium;
Journal_Title :
Visualization and Computer Graphics, IEEE Transactions on
DOI :
10.1109/2945.764868