Hierarchical spline approximation

We discuss spline refinement methods that approximate multi-valued data defined over one, two, and three dimensions. The input to our method is a coarse decomposition of the compact domain of the function to be approximated consisting of intervals (univariate case), triangles (bivariate case), and tetrahedra (trivariate case). We first describe a best linear spline approximation scheme, understood in a least squares sense, and refine on initial mesh using repeated bisection of simplices (intervals, triangles, or tetrahedra) of maximal error. We discuss three enhancements that improve the performance and quality of our basic bisection approach. The enhancements we discuss are: (i) using a finite element approach that only considers original data sites during subdivision, (ii) including first-derivative information in the error functional and spline-coefficient computations, and (iii) using quadratic (deformed, ''curved'') rather than linear simplices to better approximate bivariate and trivariate data. We improve efficiency of our refinement algorithms by subdividing multiple simplices simultaneously and by using a sparse- matrix representation and system solver