@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!

@ 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.

@ Bill: If I bound the perimeter of the spline, will I still get a solution?

@Joseph: That's why my main question is about general polynomial splines, and not about cubic splines- about which I gave only an illustration

@ Joseph: Corrected