An algorithm for data reduction using splines with free knots

A new algorithm is developed for modelling a large densely distributed data set to within a given tolerance using free knot splines. The goal is to use as few knots as possible. Our approach to this problem is to group the data by using ideas from non-linear approximation, especially the idea of balancing subintervals. We then use the least squares method to generate the desired curve. Pre-processing is used for inaccurate data. The computational expense of our algorithm compares favorably with some alternative approaches.