De Boor's algorithm: Difference between revisions

Revision as of 07:29, 18 August 2017

Revision as of 07:56, 18 August 2017

Line 1:

In the [[mathematics|mathematical]] subfield of [[numerical analysis]] '''de Boor's algorithm'''<ref name="de_boor_paper">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> is a fast and [[numerically stable]] [[algorithm]] for evaluating [[spline curve]]s in [[B-spline]] form. It is a generalization of [[de Casteljau's algorithm]] for [[Bézier curve]]s. 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.<ref>{{cite journal |last=Lee |first=E. T. Y. |date=December 1982 |title=A Simplified B-Spline Computation Routine |journal=Computing |volume=29 |issue=4 |pages=365–371 |publisher=Springer-Verlag|doi=10.1007/BF02246763}}</ref><ref>{{cite journal | author = Lee, E. T. Y. | journal = Computing | issue = 3 | pages = 229–238 | publisher = Springer-Verlag | doi=10.1007/BF02240069|title = Comments on some B-spline algorithms | volume = 36 | year = 1986}}</ref>

== Introduction ==

Line 7:

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

B-splines of order <math> p + 1 </math> are connected piece-wise polynomial functions of degree <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. Note: the [[B-spline|main article about B-splines]] and the classic publications<ref>C. de Boor [1971], name="Subroutine package for calculating with B-splinesde_boor_paper", Techn.Rep. LA-4728-MS, Los Alamos Sci.Lab, Los Alamos NM; p. 109, 121.></ref> use a different notation. The order of the B-spline is calledindexed as <math> B_{i,n}(x) </math> with <math>n = p + 1</math>.

== Local support ==

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: