<p>For a function <span class="math-container">$y = f(x)$</span> the (signed) curvature at <span class="math-container">$x$</span> is given by:
<span class="math-container">$$
\kappa(x) = \frac{f''(x)}{(1+f'^2(x))^{\frac{3}{2}}}
$$</span></p>

<p>If you assume that the slope is very small compared to <span class="math-container">$1$</span>: <span class="math-container">$ f'^2&lt;\!&lt;1 $</span>, then:</p>

<p><span class="math-container">$$ k(x) \approx f''(x)$$</span></p>

<p>Suppose you are given data points (<span class="math-container">$x_0&lt;x_1&lt;\cdots&lt;x_N$</span>):</p>

<p><span class="math-container">$$(x_0,y_0), (x_1,y_1), ..., (x_N, y_N)$$</span></p>

<p>You want to find an interpolating function <span class="math-container">$f$</span>, such that:</p>

<p><span class="math-container">$$f(x_k) = y_k$$</span></p>

<p>And we'll additionally require that it minimizes the energy:</p>

<p><span class="math-container">$$E[f] = \int_{x_0}^{x_N}\left(f''(x)\right)^2\,dx$$</span></p>

<p>Let <span class="math-container">$f(x_k) = y_k \wedge \exists f''(x) \wedge f''(x_0)=f''(x_N) = 0$</span>, and let <span class="math-container">$f$</span> be piece-wise cubic, then:
<span class="math-container">$$\forall g \ne f : g(x_k) = y_k \wedge \exists g''(x) \implies $$</span>
<span class="math-container">$$ E[g] = \int_{x_0}^{x_N}\left(g''(x)\right)^2\,dx &gt; \int_{x_0}^{x_N}\left(f''(x)\right)^2\,dx = E[f]$$</span></p>

<p>Proof:</p>

<p><span class="math-container">$$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 = $$</span></p>

<p><span class="math-container">$$ \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$$</span>
<span class="math-container">$$- 2\int_{x_0}^{x_N}\left(f''(x)\right)^2\,dx + 2\int_{x_0}^{x_N}g''(x)f''(x)\,dx = $$</span></p>

<p><span class="math-container">$$\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 $$</span></p>

<p>Clearly if <span class="math-container">$g \ne f$</span> almost everywhere then <span class="math-container">$\int_{x_0}^{x_N}\left(g''(x)-f''(x)\right)^2\,dx &gt; 0$</span>, then to prove <span class="math-container">$E[g]-E[f]&gt;0$</span> it remains to show that: <span class="math-container">$2\int_{x_0}^{x_N}(g''(x)-f''(x))f''(x)\,dx \geq 0$</span>.</p>

<p>Integrating by parts yields:</p>

<p><span class="math-container">$$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)] = $$</span></p>

<p><span class="math-container">$$ 2(g'(x_N)-f'(x_N))f''(x_N) - 2(g'(x_0)-f'(x_0))f''(x_0)$$</span>
<span class="math-container">$$-2\int_{x_0}^{x_N}(g'(x)-f'(x))f'''(x)\,dx = $$</span></p>

<p>Since <span class="math-container">$f''(x_N) = f''(x_0) = 0$</span> the first two terms are 0, and we are left with:</p>

<p><span class="math-container">$$- 2\int_{x_0}^{x_N}(g'(x)-f'(x))f'''(x)\,dx = $$</span></p>

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

<p><span class="math-container">$$-2\sum_{k=0}^{N-1}f'''([x_k,x_{k+1}))\int_{x_k}^{x_{k+1}}(g'(x)-f'(x))\,dx = $$</span></p>

<p><span class="math-container">$$-2\sum_{k=0}^{N-1}6a_k[g(x_{k+1})-f(x_{k+1}) - (g(x_k) - f(x_k))] = $$</span></p>

<p>Using the interpolation constraint <span class="math-container">$f(x_k) = g(x_k) = y_k$</span>:</p>

<p><span class="math-container">$$-2\sum_{k=0}^{N-1}6a_k[y_{k+1} - y_{k+1} - (y_k-y_k)] = 0$$</span></p>

<p>Thus:</p>

<p><span class="math-container">$$E[g] - E[f] = \int_{x_0}^{x_N}\left(g''(x)-f''(x)\right)^2\,dx &gt; 0$$</span></p>

<p>And consequently:</p>

<p><span class="math-container">$$E[g] &gt; E[f]$$</span></p>

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

<p><span class="math-container">$$ E[f] = \int_{x_0}^{x_N}\left(f''(x)\right)^2\,dx $$</span></p>

CC BY-SA 4.0
2019-09-07T22:49:00.403Z
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
CC BY-SA 4.0
2019-09-07T22:55:02.060Z
@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
CC BY-SA 4.0
2019-09-07T23:01:06.430Z
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
CC BY-SA 4.0
2019-09-08T00:40:45.330Z
@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
CC BY-SA 4.0
2019-09-07T22:33:31.893Z
2019-09-07T22:39:48.397Z
2019-09-07T22:39:48.397Z
lightxbulb
<p>Splines confuse me which is one reason I asked somebody else to write that chapter.</p>

<p>But I like this explanation:
<a href="https://www.johndcook.com/blog/2009/02/06/the-smoothest-curve-through-a-set-of-points/" rel="nofollow noreferrer">https://www.johndcook.com/blog/2009/02/06/the-smoothest-curve-through-a-set-of-points/</a></p>

CC BY-SA 4.0
2019-09-08T03:00:19.190Z
Thanks for the answer. I really like this book and also the ray tracing in weekends series.
8cold8hot
CC BY-SA 4.0
2019-09-07T19:59:44.957Z
2019-09-07T19:59:44.957Z
Peter Shirley
<p>As described by Shirley in his computer graphics book,</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>Could you please give some hints or references about its proof?</p>

CC BY-SA 4.0
2019-09-07T18:52:43.267Z
Could you mention which specific computer graphics book by Shirley you are quoting from? (There are several.)
trichoplax is on Codidact now
CC BY-SA 4.0
2019-09-08T02:58:38.843Z
It is the third version of "Fundamentals of computer graphics" published by CRC Press.
8cold8hot
<curve>
Why cubic curves provide the minimum curvature interpolants?
8cold8hot
# Why cubic curves provide the minimum curvature interpolants?

(Asked by: username_0 on 2019-09-07)

As described by username_4 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 please give some hints or references about its proof?

**Tags:** curve

> **Comments:**
> **username_1**: Could you mention which specific computer graphics book by username_4 you are quoting from? (There are several.)  
> **username_0**: It is the third version of "Fundamentals of computer graphics" published by CRC Press.  

---

## 2 answers

### Answer by username_2 on 2019-09-07. Score: 2 | Accepted answer

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\_1<\cdots<x\_N$):

$$(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 $$

> **Comments:**
> **username_3**: 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).  
> **username_2**: @username_3 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.  
> **username_3**: 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.  
> **username_2**: @username_3 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.  

---

### Answer by username_4 on 2019-09-07. Score: 2

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/>

> **Comments:**
> **username_0**: Thanks for the answer. I really like this book and also the ray tracing in weekends series.  

---

