De Boor's algorithm

In the mathematical subfield of numerical analysis de Boor's algorithm is a fast and numerically stable algorithm for evaluating spline curves in B-spline form. It is a generalization of de Casteljau's algorithm for Bézier curves. The algorithm was devised by Carl R. de Boor. Simplified, potentially faster variants of the de Boor algorithm have been created but they suffer from comparatively lower stability. In the mathematical subfield of numerical analysis de Boor's algorithm is a fast and numerically stable algorithm for evaluating spline curves in B-spline form. It is a generalization of de Casteljau's algorithm for Bézier curves. The algorithm was devised by Carl R. de Boor. Simplified, potentially faster variants of the de Boor algorithm have been created but they suffer from comparatively lower stability. A general introduction to B-splines is given in the main article. Here we discuss de Boor's algorithm, an efficient and numerically stable scheme to evaluate a spline curve S ( x ) {displaystyle mathbf {S} (x)} at position x {displaystyle x} . The curve is built from a sum of B-spline functions B i , p ( x ) {displaystyle B_{i,p}(x)} multiplied with potentially vector-valued constants c i {displaystyle mathbf {c} _{i}} , called control points, B-splines of order p + 1 {displaystyle p+1} are connected piece-wise polynomial functions of degree p {displaystyle p} defined over a grid of knots t 0 , … , t i , … , t m {displaystyle {t_{0},dots ,t_{i},dots ,t_{m}}} (we always use zero-based indices in the following). De Boor's algorithm uses O(p2) + O(p) operations to evaluate the spline curve. Note: the main article about B-splines and the classic publications use a different notation: the B-spline is indexed as B i , n ( x ) {displaystyle B_{i,n}(x)} with n = p + 1 {displaystyle n=p+1} . B-splines have local support, meaning that the polynomials are positive only in a finite domain and zero elsewhere. The Cox-de Boor recursion formula shows this: Let the index k {displaystyle k} define the knot interval that contains the position, x ∈ [ t k , t k + 1 ] {displaystyle xin } . We can see in the recursion formula that only B-splines with i = k − p , … , k {displaystyle i=k-p,dots ,k} are non-zero for this knot interval. Thus, the sum is reduced to: It follows from i ≥ 0 {displaystyle igeq 0} that k ≥ p {displaystyle kgeq p} . Similarly, we see in the recursion that the highest queried knot location is at index k + 1 + p {displaystyle k+1+p} . This means that any knot interval [ t k , t k + 1 ) {displaystyle [t_{k},t_{k+1})} which is actually used must have at least p {displaystyle p} additional knots before and after. In a computer program, this is typically achieved by repeating the first and last used knot location p {displaystyle p} times. For example, for p = 3 {displaystyle p=3} and real knot locations ( 0 , 1 , 2 ) {displaystyle (0,1,2)} , one would pad the knot vector to ( 0 , 0 , 0 , 0 , 1 , 2 , 2 , 2 , 2 ) {displaystyle (0,0,0,0,1,2,2,2,2)} . With these definitions, we can now describe de Boor's algorithm. The algorithm does not compute the B-spline functions B i , p ( x ) {displaystyle B_{i,p}(x)} directly. Instead it evaluates S ( x ) {displaystyle mathbf {S} (x)} through an equivalent recursion formula. Let d i , r {displaystyle mathbf {d} _{i,r}} be new control points with d i , 0 := c i {displaystyle mathbf {d} _{i,0}:=mathbf {c} _{i}} for i = k − p , … , k {displaystyle i=k-p,dots ,k} . For r = 1 , … , p {displaystyle r=1,dots ,p} the following recursion is applied: Once the iterations are complete, we have S ( x ) = d k , p {displaystyle mathbf {S} (x)=mathbf {d} _{k,p}} , meaning that d k , p {displaystyle mathbf {d} _{k,p}} is the desired result.