De Boor's algorithm: Difference between revisions

Revision as of 13:03, 11 August 2017

Revision as of 18:33, 11 August 2017

Line 3:

== Introduction ==

A general introduction to B-splines is given in the [[B-spline|main article]]. Here we discuss de Boor's algorithm, an efficient and numerically stable scheme to evaluate a B-spline curve <math> \mathbf{S}(x) </math> at position <math> x </math>. The curve is build from a sum of potentially vectorB-valuedspline constantsfunctions <math> \mathbfB_{ci,p}_i(x) </math>, calledmultiplied controlwith points,potentially and Bvector-splinevalued functionsconstants <math> B_\mathbf{i,pc}(x)_i </math>, called control points,

:<math> \mathbf{S}(x) = \sum_i \mathbf{c}_i B_{i,p}(x). </math>

B-splines are connected piece-wise polynomial functions of orderdegree <math> p </math> defined over a grid of knots <math> {t_0, \dots, t_i, \dots, t_m} </math> (we always use zero-based indices in the following). De Boor's algorithm uses [[Big O notation|O]](p²) + [[Big O notation|O]](p) operations to evaluate the spline curve.

== Local support ==

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<ref>C. de Boor, p. 13190</ref> shows this:

:<math>B_{i,0}(x) := \left\{

Line 31:

== The algorithm ==

With these definitions, we can now describe de Boor's algorithm<ref>C. de Boor [1971], "Subroutine package for calculating with B-splines", Techn.Rep. LA-4728-MS, Los Alamos Sci.Lab, Los Alamos NM; p. 109, 121.</ref>. 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:

Line 102:

'''Works cited'''

*{{cite book | author = Carl de Boor | title = A Practical Guide to Splines, Revised Edition | publisher = Springer-Verlag | year = 19782003|ISBN=30-540387-9035695366-93}}

[[Category:Numerical analysis]]