# Data Interpolation by Near-Optimal Splines with Free Knots Using Linear Programming
## 2 Literature Review  
Spline Applications.Splines have come in common use in multiple and diverse disciplines such as robotics and statistics. Cubic splines are used in the problem of coordination and planning of the robotic motion [12]. The trajectories for robot motion are frequently described by smooth cubic splines [13]. Cubic splines (\(r=3\)) are used to characterize the dependency of the Markov model statistical parameters on the conditional parameters [14]. Many filtering techniques require the use of splines. Splines are used to extract curves to model approximation to the shapes of segmented images that result from smoothing the lines of an object in the presence of its shape uncertainty [15]. In digital signal processing, splines are used to generate new sequences with a higher sampling rate (upsampling) [16]. Other recent spline applications include (1) operations research [17; 18; 19], (2) dynamic programming [20; 21], (3) mathematical programming [22; 23; 24], (4) statistics [25; 26; 27; 28; 29; 30; 31], (5) control theory [31; 32; 33; 34; 35; 36], (6) computer graphics [37; 38], (7) path planning [31], and (8) portfolio selection under fluctuating interest rates [20; 21].  
General Overview of Optimal Splines with Free Knots. Spline functions were introduced as early as in the nineteenth century by [PERSON] ([39], p. 165) and later by [PERSON] [40]. Since then, the subject has grown vigorously and many excellent texts are available on the subject: [25; 41; 42; 43; 44; 45].  
Studies have shown that the approximations by splines can be significantly improved if knots are allowed to be free rather than at a priori fixed locations (e.g., data points) [46]. When the knots of a spline are fixed a priori (for example, knots coincide with data points), it is called a spline with fixed knots [47; 48]. When the knots are not fixed but are determined optimally, it is called a spline with free or variable knots. Generally, as one would expect,the analysis for fixed knots tends to be simpler than for free knots [25] (p. 190). A spline that is required to pass through the data points exactly when data are fairly accurate is called an _interpolatory_ spline; otherwise, it is an _approximating_ spline. The methods given in this section focus on optimal interpolatory splines, with free knots with cubic splines being a special case. A comparative analysis showing advantages of free-knot splines over data-smoothing techniques has been given in [49]. Typically, the degree of smoothness is controlled by both the number and the position of the knots.  
It has been shown in [26] that there always exists an optimal spline with \(\left\|f^{(r)}\right\|_{\infty}=k^{*}\) for each polynomial comprising the spline and \((n-r-1)\) knots, where \(n\) is the number of data points and \(r\) is the degree of the spline that interpolates them. It is noted that, for a given value \(k^{*}\), an optimal spline with \(\left\|f^{(r)}\right\|_{\infty}=k^{*}\) is not necessarily unique (since some of the polynomials comprising the spline (but not all) that interpolate given data points may have \(\left\|f^{(r)}\right\|_{\infty}\) that is less than the optimal value \(k^{*}\)). The apparatus of the proof of the above result is complex, but a simple proof for the quadratic case \(r=2\) is given in [50].