Institute for Data Analysis and Visualization

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 (scattered-data) 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 Sobolev-like norm, leading to element-specific error values. We use these interval-/triangle-/tetrahedron-specific values to identify the element to subdivide next. The subdivision of an element with largest error value requires the re-computation 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 sparse-matrix representation and system solver.