Interpolation Splines of Bounded Curvature - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T16:01:59Z http://mathoverflow.net/feeds/question/39554 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/39554/interpolation-splines-of-bounded-curvature Interpolation Splines of Bounded Curvature Ganesh 2010-09-21T23:30:52Z 2010-09-23T01:18:14Z <p>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 &amp; 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$?</p> <p>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. </p> <p>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?</p> <p>FYI, this isn't a homework problem. I ran into this question when trying to write code for an Engineering application.</p> http://mathoverflow.net/questions/39554/interpolation-splines-of-bounded-curvature/39571#39571 Answer by Bill Thurston for Interpolation Splines of Bounded Curvature Bill Thurston 2010-09-22T01:42:59Z 2010-09-22T02:22:39Z <p>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.</p> <p>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.</p> <p>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):</p> <p><img src="http://dl.dropbox.com/u/5390048/splines.jpg" alt="alt text"></p> <p>The design considerations for splines are much more subtle than minimizing curvature. </p> <p>However, I'd like to mention that the earlier meaning of <a href="http://en.wikipedia.org/wiki/Flat_spline" rel="nofollow">splines</a> 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).</p> <p>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.</p> http://mathoverflow.net/questions/39554/interpolation-splines-of-bounded-curvature/39602#39602 Answer by Joseph O'Rourke for Interpolation Splines of Bounded Curvature Joseph O'Rourke 2010-09-22T11:59:14Z 2010-09-22T13:46:05Z <p>Perhaps there is a result along these lines?</p> <blockquote> <p>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.</p> </blockquote> <p><br /> <img src="http://cs.smith.edu/~orourke/MathOverflow/SplineArcs.jpg" alt="alt text"> <br /></p> <p>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.</p>