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 Bezier 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 whose shape is described by a sequence of p points $\mathbf{d}_0, \mathbf{d}_1, \dots, \mathbf{d}_{p-1}$ , which plays the role of a control polygon. The curve can be described as a function $\mathbf{s}(x)$ of one parameter x. To pass through the sequence of points, the curve must satisfy $\mathbf{s}(u_0)=\mathbf{d}_0, \dots, \mathbf{s}(u_{p-1})=\mathbf{d}_{p-1}$ . But this is not quite the case: in general we are satisfied that the curve "approximate" the control polygon. We assume that u₀, ..., u_p-1 are given to us along with $\mathbf{d}_0, \mathbf{d}_1, \dots, \mathbf{d}_{p-1}$ .

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 $\mathbf{d}_0, \mathbf{d}_1, \dots, \mathbf{d}_{p-1}$ , finds the value of spline curve $\mathbf{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

$\mathbf{s}(x) = \sum_{i=0}^{p-1} \mathbf{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,

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

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