De Boor's algorithm
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 curve
s. The algorithm was devised by Carl R. de Boor
. Simplified, potentially faster variants of the de Boor algorithm have been created but they suffer from comparatively lower stability.
, 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 u0, ..., up-1 are given to us along with 
.
One approach to solve this problem is by spline
s. A spline is a curve that is a piecewise nth degree polynomial. This means that, on any interval[ ui, ui+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 [ ui-1, ui) and [ ui, ui+1) meet at the point ui, 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 u0, ..., up-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.
.
We can express the curve as
where
and
Due to the spline locality property,
So the value
is determined by the control points 
; the other control points 
have no influence. De Boor's algorithm, described in the next section, is a procedure which efficiently calculates the expression for 
.
and 
for 
.
Now calculate
with
Then
.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
subfield of numerical analysis
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
the de Boor's algorithm is a fast and numerically stable algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for evaluating spline curves in B-spline
B-spline
In the mathematical subfield of numerical analysis, a B-spline is a spline function that has minimal support with respect to a given degree, smoothness, and domain partition. B-splines were investigated as early as the nineteenth century by Nikolai Lobachevsky...
form. It is a generalization of the de Casteljau's algorithm
De Casteljau's algorithm
In the mathematical field of numerical analysis, De Casteljau's algorithm is a recursive method to evaluate polynomials in Bernstein form or Bézier curves, named after its inventor Paul de Casteljau...
for Bézier curve
Bézier curve
A Bézier curve is a parametric curve frequently used in computer graphics and related fields. Generalizations of Bézier curves to higher dimensions are called Bézier surfaces, of which the Bézier triangle is a special case....
s. The algorithm was devised by Carl R. de Boor
Carl R. de Boor
Carl-Wilhelm Reinhold de Boor is a German-American mathematician and professor emeritus at the University of Wisconsin–Madison.-Early life:...
. Simplified, potentially faster variants of the de Boor algorithm have been created but they suffer from comparatively lower stability.
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 u0, ..., up-1 are given to us along with .One approach to solve this problem is by spline
Spline (mathematics)
In mathematics, a spline is a sufficiently smooth piecewise-polynomial function. In interpolating problems, spline interpolation is often preferred to polynomial interpolation because it yields similar results, even when using low-degree polynomials, while avoiding Runge's phenomenon for higher...
s. A spline is a curve that is a piecewise nth degree polynomial. This means that, on any interval
De Boor's algorithm is an algorithm which, given u0, ..., up-1 and
, finds the value of spline curve at a point x. It uses OBig O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(n2) 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.We can express the curve as
where
and
Due to the spline locality property,
So the value
is determined by the control points ; the other control points have no influence. De Boor's algorithm, described in the next section, is a procedure which efficiently calculates the expression for .The algorithm
Suppose and for .Now calculate
with
Then
.