De Boor's algorithm

In mathematics, De Boor algorithm is an algorithm for evaluating spline curves.

The general setting is as follows. We would like to construct a curve passing through a sequence of points ${\displaystyle {\vec {d}}_{0},{\vec {d}}_{1},\dots ,{\vec {d}}_{p}}$. The curve will be specified as a function ${\displaystyle {\vec {s}}(x)}$ of one parameter x. To pass through the sequence of points, the curve must satisfy ${\displaystyle {\vec {s}}(u_{0})={\vec {d}}_{0},\dots ,{\vec {s}}(u_{p})={\vec {d}}_{p}}$. We assume that u₀, ..., u_p are given to us along with ${\displaystyle {\vec {d}}_{0},{\vec {d}}_{1},\dots ,{\vec {d}}_{p}}$.

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

Goal of the algorithm

Suppose we want to evaluate the spline curve

${\displaystyle {\vec {s}}(u)=\sum _{i=-n}^{p-1}{\vec {d}}_{i}N_{i}^{n}(u),}$ 

defined on the interval ${\displaystyle [u_{0},u_{p})}$  for a parameter value ${\displaystyle x\in [u_{\ell },u_{\ell +1})}$ . Due to the spline locality property, we can write

${\displaystyle {\vec {s}}(x)=\sum _{i=\ell -n}^{\ell }{\vec {d}}_{i}N_{i}^{n}(x)}$ 

So the value ${\displaystyle {\vec {s}}(x)}$  is determined by the controlpoints ${\displaystyle {\vec {d}}_{\ell -n},{\vec {d}}_{\ell -n+1},\dots ,{\vec {d}}_{\ell }}$ ; the other control points have no influence. The goal of de Boor's algorithm is to evaluate ${\displaystyle {\vec {s}}(x)}$  efficiently.

The algorithm

Suppose ${\displaystyle x\in [u_{\ell },u_{\ell +1})}$  and ${\displaystyle {\vec {d}}_{i}^{[0]}={\vec {d}}_{i}}$  for ${\displaystyle i=\ell -n+k,\dots ,\ell }$ . Now calculate

${\displaystyle {\vec {d}}_{i}^{[k]}=(1-\alpha _{k,i}){\vec {d}}_{i-1}^{[k-1]}+\alpha _{k,i}{\vec {d}}_{i}^{[k-1]};\qquad k=1,\dots ,n;\quad i=\ell -n+k,\dots ,\ell }$ 

with

${\displaystyle \alpha _{k,i}={\frac {x-u_{i}}{u_{i+n+1-k}-u_{i}}}.}$ 

Then ${\displaystyle {\vec {s}}(x)={\vec {d}}_{\ell }^{[n]}}$ .