De Boor's algorithm: Difference between revisions

Revision as of 18:27, 5 April 2004

Revision as of 18:57, 5 April 2004

Line 1:

In [[mathematics]], '''De Boor algorithm''' is an algorithm for evaluating [[spline]] curves.

== Introduction ==

The general setting is as follows. We would like to construct a curve passing through a sequence of points <math>\vec{d}_0, \vec{d}_1, \dots, \vec{d}_p</math>. The curve will be specified as a function <math> \vec{s}(x)</math> of one parameter ''x''. To pass through the sequence of points, the curve must satisfy <math>\vec{s}(u_0)=\vec{d}_0, \dots,

\vec{s}(u_p)=\vec{d}_p</math>. We assume that ''u₀, ..., u_p'' are given to us along with <math>\vec{d}_0, \vec{d}_1, \dots, \vec{d}_p</math>.

The general setting is as follows. We would like to construct a curve passing through a sequence of ''p'' points <math>\vec{d}_0, \vec{d}_1, \dots, \vec{d}_p_{p-1}</math>. The curve willcan be specifieddesrcibed as a function <math> \vec{s}(x)</math> of one parameter ''x''. To pass through the sequence of points, the curve must satisfy <math>\vec{s}(u_0)=\vec{d}_0, \dots,

\vec{s}(u_pu_{p-1})=\vec{d}_p_{p-1}</math>. We assume that ''u₀, ..., u_p-1'' are given to us along with <math>\vec{d}_0, \vec{d}_1, \dots, \vec{d}_p_{p-1}</math>.

One approach to solving this problem is by [[spline]]s. A spline is a curve that is piecewise ''n^th'' degree polynomial. This means that, on any interval ''[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 ''[u_i-1 , u_i)'' and ''[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).

De 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''.

== Goal of the algorithm==

== GoalOutline of the algorithm==

Suppose we want to evaluate the spline curve

definedSuppose onwe thewant intervalto <math>evaluate the [u_0,u_p)spline </math>curve for a parameter value <math> x \in [u_{\ell},u_{\ell+1}) </math>.

:<math> \vec{s}(u) = \sum_{i=-n}^{p-1} \vec{d}_i N_i^n(u), </math>

We can express the curve as

defined on the interval <math> [u_0,u_p) </math> for a parameter value <math> x \in [u_{\ell},u_{\ell+1}) </math>.

:<math> \vec{s}(ux) = \sum_{i=-n}^{p-1} \vec{d}_i N_i^n(ux), </math>

Due to the spline locality property, we can write

where ''N_iⁿ(x)'' are polynomials in x with coefficients depending on ''u₀, ..., u_p'' but not <math>\vec{d}_i</math>.

Due to the spline locality property, we can write

:<math> \vec{s}(x) = \sum_{i=\ell-n}^{\ell} \vec{d}_i N_i^n(x) </math>

So the value <math>\vec{s}(x)</math> is determined by the controlpoints <math> \vec{d}_{\ell-n},\vec{d}_{\ell-n+1},\dots,\vec{d}_{\ell} </math>; the other control points <math>\vec{d}_i</math> have no influence. The goal of de Boor's algorithm, described in the next section, is toa evaluateprocedure which efficiently evaluates the expression for <math> \vec{s}(x) </math> efficiently.

== The algorithm ==

Suppose <math> x \in [u_{\ell},u_{\ell+1}) </math> and <math> \vec{d}_i^{[0]} = \vec{d}_i </math> for <math> ''i = \elll-n+k,\dots ...,\ell </math>l''.

Now calculate

:<math> \vec{d}_i^{[k]} = (1-\alpha_{k,i}) \vec{d}_{i-1}^{[k-1]} + \alpha_{k,i} \vec{d}_i^{[k-1]}; \qquad k=1,\dots,n; \quad i=\ell-n+k,\dots,\ell </math>