5.1.7 Interpolation and Splines

We need curves passing through a finite number of given points. In algebra we learn that there is exactly one polynomial $p$ of degree at most $n$ passing through $n+1$ points

$$P_0=\langle t_0,x_0\rangle,\dots,P_n=\langle t_n,x_n\rangle$$

with pairwise different $t_0,t_1,\dots,t_n$. A simple formula for obtaining this polynomial $p$ is the Lagrange interpolation formula:

$$p(x)=\sum_{k=0}^n x_k\,L_k(t)$$ where $$L_k(t):=\prod_{j\ne k}\frac{t-t_j}{t_k-t_j}$$

This is easily checked, since $L_k(t_j)=0$ for $k\ne j$ and $L_k(t_k)=1$.

For a large number of points this becomes quite lengthy to calculate and for $t$ between the given $t_j$ the values can be quite far away from the $x_j$. So the idea is to interpolate a fixed small number of successive points and piece them together.

The simplest way would be to use linear interpolation of successive points and we would thus obtain a polygon.

But we could also take 3 (, 4 or more ) successive points and take the quadratic (, cubic, ...) polynomial connecting these and piece them together.

The disadvantage of this method will be that at the points, where we paste the pieces together the curve may take sharp turns, i.e. the left-sided and right-sided derivatives may be different.

To avoid this problem Bezier curves have been invented. In order to discuss them we need the Bernstein polynomials:

$$B^n_k(t):=\binom{n}{k}t^k(1-t)^{n-k},$$

e.g.

$$B_0^0(t)=1;$$

$$B_0^1(t)=(1-t),\qquad B_1^1(t)=t;$$

$$B_0^2(t)=(1-t)^2,\qquad B_1^2(t)=2t(1-t),\qquad B_2^2(t)=t^2;$$

$$B_0^3(t)=(1-t)^3,\qquad B_1^3(t)=3t(1-t)^2,\qquad B_2^3(t)=3t^2(1-t),\qquad B_3^3(t)=t^3$$

$$\vdots$$

A recursive definition is

$$B_k^n(t):=(1-t)B_k^{n-1}+t B_{k-1}^{n-1}(t).$$

We have:

• $B_k^n(t)\geq 0$ for all $0\leq t\leq 1$.
• $\sum_{k=0}^n B_k^n(t)=1$.
• $B_k^n(t)=\sum_{i=k}^n (-1)^{i-k}\binom{n}{i}\binom{i}{k}t^i$.
• $t^k=\sum_{i=k-1}^{n-1}\binom{i}{k}/\binom{n}{k}\,B_i^n(t)$.
• From the last two equations we deduce that $(B_k^n)_{0\leq k\leq n}$ is a basis of the vector space of all polynomials of degree $\leq n$.
• $(B_k^n)'(t)=n(B_{k-1}^{n-1}(t)-B_k^{n-1}(t))$
• A formula for a linear combination $B(t)=\sum_{k=0}^n c_j B_j^n(t)$ of the Bernstein polynomials of degree 2 is given by
  $$B(t) = (1,t,t^2)\cdot \begin{pmatrix}1 & 0& 0 \\ -2 & 2 & 0 \\ 1 & -2 & 1\end{pmatrix}\cdot \begin{pmatrix}c_0 \\ c_2 \\ c_2 \end{pmatrix}.$$

Now the Bezier curve of degree $n$ given by $n+1$ many points $P_0,\dots,P_n$ is given by

$$P(t)=\sum_{j=0}^n P_j\, B_i^n(t)$$

This can be obtained recursively by

$$P_i^0(t) := P_i$$

$$P_i^j(t) := (1-t)P_{i-1}^{j-1}(t)+tP_{i}^{j-1}(t)$$

$$P(t) := P_n^n(t)$$

A geometric interpretation of this can be found in
graphics.cs.ucdavis.edu/.../Subdivision-Curves.pdf

The main properties of the Bezier curve $P$ are the following:

• $P$ is polynomial (of degree at most $n$) and hence $C^{\infty}$.
• $P(0)=P_0$ and $P(1)=P_n$.
• The tangent to $P$ at 0 is the line $\overline{P_0P_1}$.
• The tangent to $P$ at $1$ is the line $\overline{P_{n-1}P_n}$.
• The curve $P$ lies in convex hull of $\{P_0,P_1,\dots,P_n\}$, note, however, that the points $P_1,\dots,P_{n-1}$ will not ly on $P$. They are only points which control the shape of the curve $P$.