Interpolation Splines of Bounded Curvature - MathOverflow

Interpolation Splines of Bounded Curvature

2010-09-21T23:30:52Z

Given $n$ points $p_i=(x_i,y_i)$ on the [Euclidean] plane, and a positive real number $\rho$. Can we have a polynomial spline (e.g natural cubic spline) passing through all these points, such that: (a) successive segments of the spline have are continuous and have equal 1st & 2nd derivative at the meeting point (Eg . If $S_1(x)$ joins $p_1-p_2$ and $S_2(x)$ joins $p_2-p_3$, then $S_1''(x_2)=S_2''(x_2)$.) and (b) the curvature of the spline is bounded above by $\rho$?

Note that Natural polynomial splines obey (a) but it's hard to say anything about (b). I am also unaware of any means to bound the curvature of a spline, and a literature search online didn't turn up much of interest.

Here are 2 other variations of the question above that I am unable to answer: (V1) If the spline needs to be closed, i.e. $p_{n+1}=p_1$, how, if at all,does the answer change? (V2) If we allow any type of interpolation spline at all that obeys (a) and (b), do we have a solution?

FYI, this isn't a homework problem. I ran into this question when trying to write code for an Engineering application.

Answer by Bill Thurston for Interpolation Splines of Bounded Curvature

2010-09-22T01:42:59Z

If there are no more constraints, then you can do it with arbitrarily low curvature with any reasonable class of splines. If the points are say within a 10cm region, make huge loops 1km in diameter (or bigger if you want smaller curvature). If the spline construction is smooth, continuous, and invariant under similarity, then the curvature converges to 0.

If the curves are required to stay in a bounded region of the plane, then as the region gets smaller, not even arbitrary $C^2$ curves can thread through them with bounded curvature. Just imagine $3$ points at the corners of an equilateral triangle 1 micron on a side, and ask for the curve to be confined to a box 2 microns on a side. The curvature will be on the order of $\pi / $ micron.

Here are two copies of a set of four points threaded with Adobe Illustrator splines to illustrate the phenomenon. Note: I added extra knots in the big loops to make them look better, but this isn't necessary to construct examples. (The mathematical characterization of these splines is not relevant to the answer, and furthermore, I don't actually know):

The design considerations for splines are much more subtle than minimizing curvature.

However, I'd like to mention that the earlier meaning of splines had to do with thin splints of wood used in woodworking, e.g. boat building, to lay out curves for cutting. Unlike the usual mathematical splines, they have fixed length, and a reasonable mathematical model is that they trace out curves that locally minimize total curvature subject to their constraints (lead weights called ducks because that's what they resembled).

It's easy to get examples of these traditional splines with multiple local minima: cut a strip of paper (good enough for this) and bring the ends closer without turning them. The strip pops to one side or the other, giving two local minima.

Answer by Joseph O'Rourke for Interpolation Splines of Bounded Curvature

2010-09-22T11:59:14Z

Perhaps there is a result along these lines?

Given any set of distinct points in the plane, there exists a simple (nonintersecting) path through them in a specified order, with the path composed of smoothly joined arcs of circles of the same radius $r$, where $r$ is some function of the minimum point separation.

This is likely useless for any application, but it might make a nice theorem, especially if the largest $r$ could be achieved or at least approached.