Fast L1kCk polynomial spline interpolation algorithm with shape-preserving properties

In this article, we address the problem of interpolating data points by regular L-1-spline polynomial curves of smoothness C-k, k >= 1, that are invariant under rotation of the data. To obtain a C-1 cubic interpolating curve, we use a local minimization method in parallel on five data points belonging to a sliding window. This procedure is extended to create C-k-continuous L-1 splines, k >= 2, on larger windows. We show that, in the C-k-continuous (k >= 1) interpolation case, this local minimization method preserves the linear parts of the data well, while a global L-1 minimization method does not in general do so. The computational complexity of the procedure is linear in the global number of data points, no matter what the order C-k of smoothness of the curve is. (C) 2010 Elsevier B.V. All rights reserved.