Interpolation using a fast spline transform (FST)

The problem of interpolating data points using a smooth function has many e xisting solutions. In particular, the use of piecewise polynomials (splines ) has provided solutions with user control of smoothness, In this paper we examine the relationship between computational complexity and the degree of smoothness associated with particular spline solutions. We discuss new eff icient computational algorithms for existing C-0, C-1 and Ca continuity spl ine solutions. We also introduce a new interpolation procedure which utiliz es multiple-knot splines, The technique solves the inverse problem and rend ers the interpolating spline function, using fixed-point shifts and additio ns. In applications requiring parallel computation, the use of these simple r operations implies a significant reduction in hardware complexity.