title: On a construction of a hierarchy of best linear spline approximations using a finite element approach.
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 (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 recomputation of all spline coefficients due to the global nature of the problem. We improve efficiency by 1) subdividing multiple elements simultaneously and 2) by using a sparse-matrix representation and system solver.
authors.affiliation: Center for Processing and Integrated Computing, Department of Computer Science, University of California, Davis, CA 95616-8562, USA. wiley@cs.ucdavis.edu
authors.forename: David F
authors.initials: DF
authors.lastname: Wiley
authors.forename: Martin
authors.initials: M
authors.lastname: Bertram
authors.forename: Bernd
authors.initials: B
authors.lastname: Hamann
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D003196:Computer Graphics; D003198:Computer Simulation; D020342:Finite Element Analysis; D007089:Image Enhancement / Q000379:methods*; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D021621:Imaging, Three-Dimensional / Q000379:methods*; D016247:Information Storage and Retrieval / Q000379:methods; D016014:Linear Models; D009716:Numerical Analysis, Computer-Assisted; D012815:Signal Processing, Computer-Assisted; D014584:User-Computer Interface