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.