De Boor's Algorithm - Introduction

Introduction

The general setting is as follows. We would like to construct a curve whose shape is described by a sequence of p points, which plays the role of a control polygon. The curve can be described as a function 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 "approximates" the control polygon. We assume that u₀, ..., u_p-1 are given to us along with .

One approach to solve this problem is by splines. A spline is a curve that is a piecewise nth 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 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's algorithm is an algorithm which, given u₀, ..., u_p-1 and, finds the value of spline curve at a point x. It uses O(n2) operations. Notice that the running time of the algorithm depends only on degree n and not on the number of points p.

Read more about this topic: De Boor's Algorithm

Famous quotes containing the word introduction:

“For better or worse, stepparenting is self-conscious parenting. You’re damned if you do, and damned if you don’t.”
—Anonymous Parent. Making It as a Stepparent, by Claire Berman, introduction (1980, repr. 1986)

“The role of the stepmother is the most difficult of all, because you can’t ever just be. You’re constantly being tested—by the children, the neighbors, your husband, the relatives, old friends who knew the children’s parents in their first marriage, and by yourself.”
—Anonymous Stepparent. Making It as a Stepparent, by Claire Berman, introduction (1980, repr. 1986)

“For the introduction of a new kind of music must be shunned as imperiling the whole state; since styles of music are never disturbed without affecting the most important political institutions.”
—Plato (c. 427–347 B.C.)