Splines

A general \(N\) dimensional tensor product B-spline is given by

\[S(x_1, ..., x_N) = \sum_{i_1=0}^{n_1-1} \cdots \sum_{i_N=0}^{n_N-1} c_{i_1, ..., i_N} \prod_{j = i}^{N} B_{i_j;k_j,t_j}(x_j)\]

where \(B_{i_j;k_j,t_j}\) is the \(i_j\)-th B-spline basis function of degree \(k_j\) over the knots \({t_j}\) for the \(j\)-th dimension. Univariate and bivariate splines are special cases of this general form. The usual form for a univariate B-spline is

\[S(x) = \sum_{i=0}^{n-1} c_i B_{i;k,t} (x)\]

which takes the generalized form by letting \(N=1\), and indexing \(i\), \(k\), \(t\), \(n\), and \(x\) by a subscript 1, for the first and only dimension. Similarly, the usual form for a bivariate spline is

\[S(x, y) = \sum_{i=0}^{n_x -1} \sum_{j=0}^{n_y -1} c_{i,j} B_{i; k_x, t_x} (x) B_{j; k_y, t_y} (y)\]

which takes the generalized form if \(x=x_1\), \(y=x_2\), \(i = i_1\), \(j=i_2\), and using \(x\) and \(y\) subscripts to indicate the data for each dimension.

Order of B-Spline

A \(k=0\) degree B-spline is piecewise constant, which can be used for “nearest-neighbor” interpolation. A \(k=1\) degree B-spline is piecewise linear. A \(k=3\) degree B-spline is the default and produces aesthetically pleasing curves that can also be represented as the solution to thin-beam bending mechanics.

For an \(N\)-dimensional tensor-product B-spline, each dimension can have its own order.

Compact Support

A key feature of the B-splines is that for \(n+k+1\) knots, there are \(n\) basis functions, but only \(k+1\) are non-zero on any particular span between knots. So to interpolate a large data set requires only evaluating the linear combination of \(k+1\) elements (for each dimension). For example, a 1-dimensional interpolant can be evaluated as

\[S (x) = \sum_{i = \ell}^{\ell+k+1} c_i B_{i;k,t} (x)\]

where \(B_{i;k,t}\) is the \(i\) -th basis function, \(c_i\) is the \(i\) -th coefficient, and \(\ell\) is the first index with a non-zero basis function at \(x\). The sum could easily run over all \(n\) elements, but most summands are zero. The evaluation to be computed very efficiently by performing the minimal number of floating-point operations.

Basis definition

Each basis function is defined by a recursive relationship in the order of the B-spline. The 0-th degree B-spline has the form

\[B_{i, 0}(x) = 1, \textrm{if $t_i \le x < t_{i+1}$, otherwise $0$,}\]

and higher degree B-splines are constructed as

\[B_{i, k}(x) = \frac{x - t_i}{t_{i+k} - t_i} B_{i, k-1}(x) + \frac{t_{i+k+1} - x}{t_{i+k+1} - t_{i+1}} B_{i+1, k-1}(x)\]