# Why cubic curves provide the minimum curvature interpolants?

As described by Shirley in his computer graphics book,

Cubic curves provide the minimum-curvature interpolants to a set of points. That is, if you have a set of n + 3 points and define the “smoothest” curve that passes through them (that is the curve that has the minimum curvature over its length), this curve can be represented as a piecewise cubic with n segments.

• Could you mention which specific computer graphics book by Shirley you are quoting from? (There are several.) – trichoplax Sep 7 '19 at 18:52
• It is the third version of "Fundamentals of computer graphics" published by CRC Press. – 8cold8hot Sep 8 '19 at 2:58

For a function $$y = f(x)$$ the (signed) curvature at $$x$$ is given by: $$\kappa(x) = \frac{f''(x)}{(1+f'^2(x))^{\frac{3}{2}}}$$

If you assume that the slope is very small compared to $$1$$: $$f'^2<\!<1$$, then:

$$k(x) \approx f''(x)$$

Suppose you are given data points ($$x_0):

$$(x_0,y_0), (x_1,y_1), ..., (x_N, y_N)$$

You want to find an interpolating function $$f$$, such that:

$$f(x_k) = y_k$$

And we'll additionally require that it minimizes the energy:

$$E[f] = \int_{x_0}^{x_N}\left(f''(x)\right)^2\,dx$$

Let $$f(x_k) = y_k \wedge \exists f''(x) \wedge f''(x_0)=f''(x_N) = 0$$, and let $$f$$ be piece-wise cubic, then: $$\forall g \ne f : g(x_k) = y_k \wedge \exists g''(x) \implies$$ $$E[g] = \int_{x_0}^{x_N}\left(g''(x)\right)^2\,dx > \int_{x_0}^{x_N}\left(f''(x)\right)^2\,dx = E[f]$$

Proof:

$$E[g] - E[f] = \int_{x_0}^{x_N}\left(g''(x)\right)^2\,dx - \int_{x_0}^{x_N}\left(f''(x)\right)^2\,dx =$$

$$\int_{x_0}^{x_N}\left(g''(x)\right)^2\,dx -2\int_{x_0}^{x_N}g''(x)f''(x)\,dx + \int_{x_0}^{x_N}\left(f''(x)\right)^2\,dx$$ $$- 2\int_{x_0}^{x_N}\left(f''(x)\right)^2\,dx + 2\int_{x_0}^{x_N}g''(x)f''(x)\,dx =$$

$$\int_{x_0}^{x_N}\left(g''(x)-f''(x)\right)^2\,dx + 2\int_{x_0}^{x_N}(g''(x)-f''(x))f''(x)\,dx$$

Clearly if $$g \ne f$$ almost everywhere then $$\int_{x_0}^{x_N}\left(g''(x)-f''(x)\right)^2\,dx > 0$$, then to prove $$E[g]-E[f]>0$$ it remains to show that: $$2\int_{x_0}^{x_N}(g''(x)-f''(x))f''(x)\,dx \geq 0$$.

Integrating by parts yields:

$$2\int_{x_0}^{x_N}(g''(x)-f''(x))f''(x)\,dx = 2\int_{x_0}^{x_N}f''(x)\,d[g'(x)-f'(x)] =$$

$$2(g'(x_N)-f'(x_N))f''(x_N) - 2(g'(x_0)-f'(x_0))f''(x_0)$$ $$-2\int_{x_0}^{x_N}(g'(x)-f'(x))f'''(x)\,dx =$$

Since $$f''(x_N) = f''(x_0) = 0$$ the first two terms are 0, and we are left with:

$$- 2\int_{x_0}^{x_N}(g'(x)-f'(x))f'''(x)\,dx =$$

Since $$f$$ was chosen to be piece-wise cubic, then $$f(x) = a_kx^3 + b_kx^2 + c_kx + d_k, x \in [x_k,x_{k+1})$$ and consequently $$f'''([x_k,x_{k+1})) = 6a_k = \operatorname{const}$$, and we can take it out of the integral and integrate in each interval $$[x_k,x_{k+1}]$$:

$$-2\sum_{k=0}^{N-1}f'''([x_k,x_{k+1}))\int_{x_k}^{x_{k+1}}(g'(x)-f'(x))\,dx =$$

$$-2\sum_{k=0}^{N-1}6a_k[g(x_{k+1})-f(x_{k+1}) - (g(x_k) - f(x_k))] =$$

Using the interpolation constraint $$f(x_k) = g(x_k) = y_k$$:

$$-2\sum_{k=0}^{N-1}6a_k[y_{k+1} - y_{k+1} - (y_k-y_k)] = 0$$

Thus:

$$E[g] - E[f] = \int_{x_0}^{x_N}\left(g''(x)-f''(x)\right)^2\,dx > 0$$

And consequently:

$$E[g] > E[f]$$

Which proves the fact that an interpolating C2 cubic spline with natural end conditions minimizes the squared (approximate) "curvature" energy:

$$E[f] = \int_{x_0}^{x_N}\left(f''(x)\right)^2\,dx$$

• Minor nit: you don't need $g \neq f$ almost everywhere; you just need that to be true more than almost nowhere (i.e. on a set of strictly positive measure). – Nathan Reed Sep 7 '19 at 22:49
• @NathanReed I am not sure 'almost nowhere' is a term but I got what you mean. You are correct, since I require the functions to not agree only a measurable subset of the interval for $>$ to hold. Good catch. I won't edit it, since it may become confusing me trying to explain what almost nowhere is. I hope interested readers will see your comment below. – lightxbulb Sep 7 '19 at 22:55
• As a matter of fact, since $f$ and $g$ are required to be continuous, I think it suffices to require $g \neq f$ somewhere. That would automatically imply $g \neq f$ on a nonzero interval around that point. – Nathan Reed Sep 7 '19 at 23:01
• @NathanReed Which brings us to another point - that it's $f'' \ne g''$ which is required and not $f \ne g$ (though this is sufficient). There's no continuity constraint on $g''$ on the other hand, so the "almost nowhere" constraint is valid for this. I wonder whether it's beneficial including that in the answer however. – lightxbulb Sep 8 '19 at 0:40

Splines confuse me which is one reason I asked somebody else to write that chapter.

But I like this explanation: https://www.johndcook.com/blog/2009/02/06/the-smoothest-curve-through-a-set-of-points/

• Thanks for the answer. I really like this book and also the ray tracing in weekends series. – 8cold8hot Sep 8 '19 at 3:00