---
tag: 99SCT623E8
kind: definition
name: de Boor's algorithm
msc: [65D07, 41A15, 65D17]
defines: 5JHFB384BF
uses: [62AFX32JGT, WVD069C7QF, 21SXYJYC59]
sources:
  - url: https://en.wikipedia.org/wiki/De_Boor%27s_algorithm
---

## Definition

Let $k \ge 1$ be an order and let $(t_i)$ be a nondecreasing knot sequence.
Let $s = \sum_i c_i B_{i,k}$, where $B_{i,k}$ are the [[B-splines|62AFX32JGT]] of order $k$ and the $c_i$ are real numbers or points of $\R^d$.
Let $x$ be a point with $t_j \le x < t_{j+1}$.
*De Boor's algorithm* computes $s(x)$ as follows.

1. Set $c_i^{[0]} = c_i$ for $i = j - k + 1, \dots, j$.
2. For $r = 1, \dots, k - 1$ and $i = j - k + 1 + r, \dots, j$, set
$$\alpha_{i,r} = \frac{x - t_i}{t_{i+k-r} - t_i}, \qquad c_i^{[r]} = (1 - \alpha_{i,r})\, c_{i-1}^{[r-1]} + \alpha_{i,r}\, c_i^{[r-1]}.$$
3. Return $c_j^{[k-1]}$, which equals $s(x)$.

## Remarks

The denominators are positive, since $t_i \le t_j < t_{j+1} \le t_{i+k-r}$ in the stated range, and $\alpha_{i,r} \in [0, 1]$, so each step is a [[convex combination|21SXYJYC59]].
Correctness follows from the [[Cox–de Boor recursion|WVD069C7QF]]: one step rewrites $\sum_i c_i B_{i,k}(x)$ as $\sum_i c_i^{[1]} B_{i,k-1}(x)$, and at order $1$ only $B_{j,1}(x) = 1$ survives.
Example: $k = 2$, knots $t_0 = 0, t_1 = 1, t_2 = 2$, $x = 1/2$, so $j = 0$; then $\alpha_{0,1} = 1/2$ and $s(1/2) = (c_{-1} + c_0)/2$, which is the piecewise linear interpolant at the midpoint.
Non-example: for $x$ outside $[t_j, t_{j+1})$ the same formulas with this $j$ do not give $s(x)$ in general, because other B-splines are active there.
The cost is $O(k^2)$ operations per point.