TitleOn a Construction of a Hierarchy of Best Linear Spline Approximations using Repeated Bisection (Article)
inIEEE 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
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 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 re-computation 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.