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 ap- proach. The enhancements we discuss are: (i) using a -nite element approach that only considers original data sites during subdivision, (ii) including -rst-derivative information in the error functional and spline-coe+-cient computations, and (iii) using quadratic (deformed, \curved'') rather than linear simplices to better ap- proximate bivariate and trivariate data. We improve e+-ciency of our re-nement algorithms by subdividing multiple simplices simultaneously and by using a sparse- matrix representation and system solver