I have some odd constraints in my project. Suppose we want to use Cubic BSplines to approximate a set of Points. There is two Constraints:

  1. error value should be an input to the algorithm (error bounded).
  2. our algorithm should produce fewest curve segments. it means we have to have minimum subdivisions in the domain [0,1].

I have not very strong backgrounds in Math. Is our constraints make sense and are they reasonable? is there any works or references that can help me in this project?


Yes, your problem makes sense, and in fact it's a fairly common one. Basically, you want the simplest curve (fewest segments) that gives you an adequate fit to the points.

I don't know any way to do this except iteratively. You take a spline that has some specific set of "knots" (the values at which the spline divisions occur), and you fit this spline as best you can to the data points. Then you measure the error. If it's greater than your allowable error, you add more knots and try again. Keep going until you achieve the desired error.

There are two details to think about: how to do the fitting, and how to add more knots.

The fitting can be done by a standard least-squares algorithm. Once the knots are fixed, the least-squares computation is linear -- you can construct the curve by solving a system of linear equations. Details can be found here, and you will find lots more if you search for "least squares fitting of splines". Even if you can't understand the math, you may be able to find some code that you can use -- this is a common problem, and plenty of code is available. For example, an answer to this question has Python code, and there's a MATLAB function here.

There are a couple of different strategies for adding new knots. The most common approach is to add a new knot at the parameter value where the curve deviates most from a data point. Another idea is to add knots mid-way between the existing ones. Yet another approach is to use equally-spaced knots, and increase their number until your tolerance is achieved.

As the comment from @Rahul indicates, this approach will not give you an optimal curve. But, in my experience, it will give you a pretty good one, and it can be implemented fairly easily by using available least-squares fitting code. So, not optimal, but fairly simple, and probably adequate.

  • $\begingroup$ Nice answer, but strictly speaking I don't think you can get the optimal solution without an additional "optimize the location of the knots" step. $\endgroup$
    – user856
    Jan 2 '16 at 2:32
  • $\begingroup$ @Rahul. Correct. But, given the OP's situation, I thought he (or she) would prefer simplicity rather than optimality. Optimizing knot placement is a nasty problem, and it's pretty hard to find code that helps (as far as I know). Another flaw in my approach is that minimizing least-squares error is not the same thing as minimizing maximum error. But, again, I favored simplicity. $\endgroup$
    – bubba
    Jan 2 '16 at 2:43
  • $\begingroup$ Just noticed the photo -- the OP is "he", not "she". $\endgroup$
    – bubba
    Jan 2 '16 at 3:02
  • $\begingroup$ Very nice and comprehensive! let me ask another question :). As i know, number of knots is constant and computed based on the number of points and the degree of the curve (Cubic curves in my case). so what do you mean by "adding knots",cause the number of knots are constant? $\endgroup$ Jan 2 '16 at 10:46
  • $\begingroup$ The number of knots is constant if you want a spline that interpolates (passes through) the data points. But in least-squares fitting, the number of knots can be anything you want. For example, you might start out with the knots $(0,0,0,0,1,1,1,1)$ which will give you cubic spline with a single segment. $\endgroup$
    – bubba
    Jan 3 '16 at 3:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.