De Boor Algorithm

Article Index for
De

Information About

De Boor Algorithm

INTRODUCTION

The general setting is as follows. We would like to construct a curve passing through a sequence of ''p'' points

ec{d}_0, ec{d}_1, \dots, ec{d}_{p-1}

. The curve can be described as a function

ec{s}(x)

of one parameter ''x''. To pass through the sequence of points, the curve must satisfy

ec{s}(u_0)=ec{d}_0, \dots,
ec{s}(u_{p-1})=ec{d}_{p-1}

. We assume that ''u₀, ..., u_p-1'' are given to us along with

ec{d}_0, ec{d}_1, \dots, ec{d}_{p-1}

. This problem is called Interpolation .

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

ec{d}_0, ec{d}_1, \dots, ec{d}_{p-1}

, finds the value of spline curve

ec{s}(x)

at a point ''x''. It uses 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

Suppose we want to evaluate the spline curve for a parameter value

x \in [u_{\ell},u_{\ell+1})

.
We can express the curve as

:

ec{s}(x) = \sum_{i=0}^{p-1} ec{d}_i N_i^n(x) ,

where

N_i^r(x)=rac{x-u_i}{u_{i+n}-u_i}N_i^{r-1}(x) - rac{x-u_{i+n+1}}{u_{i+n+1}-u_{i+1}}N_{i+1}^{r-1}(x) ,

and

N_i^0(x)=\left\{\begin{matrix} 1, & \mbox{if }x \in [u_{\ell},u_{\ell+1}) \ 0, & \mbox{otherwise } \end{matrix}
ight.

Due to the spline locality property,
:

ec{s}(x) = \sum_{i=\ell-n}^{\ell} ec{d}_i N_i^n(x)

So the value

ec{s}(x)

is determined by the controlpoints

ec{d}_{\ell-n},ec{d}_{\ell-n+1},\dots,ec{d}_{\ell}

; the other control points

ec{d}_i

have no influence. De Boor's algorithm, described in the next section, is a procedure which efficiently evaluates the expression for

ec{s}(x)

.

THE ALGORITHM

Suppose

x \in

and

ec{d}_i^{[0 } = ec{d}_i

for ''i = l-n, ..., l''.
Now calculate
:

} + \alpha_{k,i} ec{d}_i^{[k-1]}; \qquad k=1,\dots,n; \quad i=\ell-n+k,\dots,\ell

with
:

\alpha_{k,i} = rac{x-u_i}{u_{i+n+1-k}-u_i}.

Then

ec{s}(x) = ec{d}_{\ell}^{

{Link without Title} } .