Editing De Boor's algorithm (section)

== The algorithm ==

With these definitions, we can now describe de Boor's algorithm. The algorithm does not compute the B-spline functions <math> B_{i,p}(x) </math> directly. Instead it evaluates <math> \mathbf{S}(x) </math> through an equivalent recursion formula.

Let <math> \mathbf{d}_{i,r} </math> be new control points with <math> \mathbf{d}_{i,0} := \mathbf{c}_{i} </math> for <math> i = k-p, \dots, k</math>. For <math> r = 1, \dots, p </math> the following recursion is applied:
<math display="block"> \mathbf{d}_{i,r} = (1-\alpha_{i,r}) \mathbf{d}_{i-1,r-1} + \alpha_{i,r} \mathbf{d}_{i,r-1}; \quad i=k-p+r,\dots,k </math>
<math display="block"> \alpha_{i,r} = \frac{x-t_i}{t_{i+1+p-r}-t_i}.</math>

Once the iterations are complete, we have <math>\mathbf{S}(x) = \mathbf{d}_{k,p} </math>, meaning that <math> \mathbf{d}_{k,p} </math> is the desired result.

De Boor's algorithm is more efficient than an explicit calculation of B-splines <math> B_{i,p}(x) </math> with the Cox-de Boor recursion formula, because it does not compute terms which are guaranteed to be multiplied by zero.