De Boor's algorithm: Difference between revisions

Revision as of 20:56, 3 October 2005

Revision as of 20:26, 26 May 2006

Line 1:

In the [[mathematics|mathematical]] subfield of [[numerical analysis]] the '''Dede Boor algorithm''' 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.

== Introduction ==

Line 8:

One approach to solving this problem is by [[spline (mathematics)|spline]]s. A spline is a curve that is piecewise ''n^th'' degree polynomial. This means that, on any interval ''<nowiki>[</nowiki>u_i, u_i+1)'', the curve must be equal to a polynomial of degree at most ''n''. It may be equal to a different polynomials on different intervals. The polynomials must be ''synchronized'': when the polynomials from intervals ''<nowiki>[</nowiki>u_i-1, u_i)'' and ''<nowiki>[</nowiki>u_i, u_i+1)'' meet at the point ''u_i'', they must have the same value at this point and their derivatives must be equal (to ensure that the curve is smooth).

Dede Boor algorithm is an algorithm which, given ''u₀, ..., u_p-1'' and <math>\vec{d}_0, \vec{d}_1, \dots, \vec{d}_{p-1}</math>, finds the value of spline curve <math>\vec{s}(x)</math> at a point ''x''. It uses [[Big O notation|O]](n²) operations. Notice that the running time of the algorithm depends only on degree ''n'' and not on the number of points ''p''.

== Outline of the algorithm==