De Boor's algorithm

From Wikipedia, the free encyclopedia

In the mathematical subfield of numerical analysis the de Boor's algorithm is a fast and numerically stable algorithm for evaluating spline curves in B-spline form. It is a generalization of the de Casteljau's algorithm for Bézier curves. The algorithm was devised by Carl R. de Boor.

1 Introduction
2 Outline of the algorithm
3 The algorithm
4 See also
5 External links

[edit] Introduction

The general setting is as follows. We would like to construct a curve passing through a sequence of p points $\vec{d}_0, \vec{d}_1, \dots, \vec{d}_{p-1}$ . The curve can be described as a function $\vec{s}(x)$ of one parameter x. To pass through the sequence of points, the curve must satisfy $\vec{s}(u_0)=\vec{d}_0, \dots, \vec{s}(u_{p-1})=\vec{d}_{p-1}$ . We assume that u₀, ..., u_p-1 are given to us along with $\vec{d}_0, \vec{d}_1, \dots, \vec{d}_{p-1}$ . This problem is called interpolation.

One approach to solving this problem is by splines. 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 $\vec{d}_0, \vec{d}_1, \dots, \vec{d}_{p-1}$ , finds the value of spline curve $\vec{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.

[edit] 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

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

where $N_i^n(x)=\frac{x-u_i}{u_{i+n}-u_i}N_i^{n-1}(x) - \frac{x-u_{i+n+1}}{u_{i+n+1}-u_{i+1}}N_{i+1}^{n-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}\right.$

Due to the spline locality property,

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

So the value $\vec{s}(x)$ is determined by the control points $\vec{d}_{\ell-n},\vec{d}_{\ell-n+1},\dots,\vec{d}_{\ell}$ ; the other control points $\vec{d}_i$ have no influence. de Boor's algorithm, described in the next section, is a procedure which efficiently evaluates the expression for $\vec{s}(x)$ .