3
$\begingroup$

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 (E.g., 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.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ @Ganesh: Do you also want equal 1st derivatives at the joins? It would be a bit odd to insist on equal 2nd derivatives but not equal 1st...? $\endgroup$
    – Joseph O'Rourke
    Commented Sep 22, 2010 at 0:00
  • $\begingroup$ @ Joseph: Corrected $\endgroup$
    – Ganesh
    Commented Sep 22, 2010 at 0:11
  • 2
    $\begingroup$ @Ganesh: Thanks for clarifying. But then do not the constraints of joining with those derivatives equal already consume all the freedom of a cubic spline? It would seem you need, say, 4th-degree polynomials, to allow room for the curvature constraint on top of the smooth-joining constraints. Perhaps I am miscounting degrees of freedom... $\endgroup$
    – Joseph O'Rourke
    Commented Sep 22, 2010 at 0:25
  • $\begingroup$ @Joseph: That's why my main question is about general polynomial splines, and not about cubic splines- about which I gave only an illustration $\endgroup$
    – Ganesh
    Commented Sep 22, 2010 at 0:29
  • $\begingroup$ @Ganesh, ah, I read the parenthetical e.g. as illustrating the problem. I see now. And after all this clarification, I am not sure I have a substantive remark. Sorry! $\endgroup$
    – Joseph O'Rourke
    Commented Sep 22, 2010 at 0:40

2 Answers 2

Reset to default
3
$\begingroup$

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):

alt text http://dl.dropbox.com/u/5390048/splines.jpg

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ @ Bill: If I bound the perimeter of the spline, will I still get a solution? $\endgroup$
    – Ganesh
    Commented Sep 22, 2010 at 3:21
  • $\begingroup$ @Ganesh: There can be many variations of this questions, with different constraints and different kinds of splines. In the Illustrator splines, one gets little splines with high curvature by making the tangent vectors short. If you constrained the degree and keep the first and 2nd derivatives bounded away from zero, then they couldn't have a small perimeter. What is your application, what are you trying to accomplish with the splines? $\endgroup$
    – Bill Thurston
    Commented Sep 22, 2010 at 3:47
  • 1
    $\begingroup$ @ Bill: I'm trying to determine paths for a car-shaped robot traversing a set of waypoints in an environment - which are the given $p_i$'s. Previous approaches, like <a href="planning.cs.uiuc.edu/node821.html"> Dubins paths </a> had discontinuous accelerations at the meeting points. Such a curve is impossible for a robotic car to navigate - therefore the second derivative requirement. Ideally, any splines (or more generally, any paths at all) I have in mind have: (a) bounded curvature (b) bounded perimeter and (c) are easy to compute, e.g. polynomial splines of small degree. $\endgroup$
    – Ganesh
    Commented Sep 22, 2010 at 23:45
  • $\begingroup$ @Ganesh: I was wondering about this kind of application, although I was imagining human-driven cars. Can the robotic cars stop and reverse direction, do you want them to always travel forward at a steady speed, or what? I'm imagining in the real application, the waypoints are actually fairly sensible, not just random points/directions. Is that right? I'll try to give a little thought to the real problem. $\endgroup$
    – Bill Thurston
    Commented Sep 23, 2010 at 0:38
  • $\begingroup$ @Bill: Though the car can reverse and change direction, the ideal case will be to have it execute one single closed path through all the points, travelled in the forward direction. And yes, the waypoints can in general be assumed fairly sensible. I am trying to get worst case results as well to get at the limits of this approach. I'd be grateful if you respond with any insights. Thank you! $\endgroup$
    – Ganesh
    Commented Sep 23, 2010 at 1:14
1
$\begingroup$

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.


alt text

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .