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