Fast L_1~kC~k 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.