

Title  On a construction of a hierarchy of best linear spline approximations using a finite element approach
(Article) 
in  IEEE Transactions on Visualization and Computer Graphics 
Author(s) 
David F. Wiley, Martin Bertram, Bernd Hamann 
Keyword(s)  Approximation; Finite element method; Grid generation; Multiresolution method; Optimization; Ritz approximation; Scattered data; Spline; Triangulation; 
Year 
2004

Download  
BibTeX  
Abstract 
We present a method for the hierarchical approximation
of functions in one, two, or three variables based on the finite element method (Ritz approximation). Starting with a set of data sites with associated function, we first determine a smooth (scattereddata) interpolant. Next, we construct an initial triangulation by triangulating the region bounded by the minimal subset of data sites defining the convex hull of all sites. We
insert only original data sites, thus reducing storage
requirements. For each triangulation we solve a minimization problem: computing the best linear spline approximation of the interpolant of all data, based on a functional involving function values and first derivatives. The error of a best linear spline approximation is computed in a Sobolevlike norm, leading to elementspecific error values. We use these
interval/triangle/tetrahedronspecific values to identify the element to subdivide next. The subdivision of an element with largest error value requires the recomputation of all spline coefficients due to the global nature of the problem. We improve efficiency by (i) subdividing multiple elements simultaneously and (ii) by using a sparsematrix representation and system
solver.
