Minimize the number of points in a piecewise linear approximation I have $m$ data points $(x_i,y_i)$ in a given interval. I would like to find a piecewise linear function $f(x)$ that approximate these $m$ points with a minimum number of points $n$ so that my approximation error is below a tolerance $\epsilon$.
My $m$ points:

The function $f$ is a piecewise linear function defined with $n$ points $(x_a^{i},y_a^{i})$. For $n=4$, it would look like:

Approximation error:
$$\frac{1}{m} \sum_{1\le i\le m}(y_i-f(x_i))^2 \leq\epsilon$$
To solve that problem I need to find, for a given $n$, a way to obtain the optimal set of points $(x_a^{i},y_a^{i})$. I can try to minimize my approximation error with gradient descent, but the function is non-convex, so it might not converge to the global optimum.
If I solve the previous step, I can simply simply run the algorithm from $n=1,2,3,...$ and stop when my approximation error drops below $\epsilon$
I sounds like a rather common problem that perhaps already has a solution. Do you know of one, or can you propose an approach to that problem?

I don't know if it converges to a minimum, but once I made a function to "convert" GPS points into a road.
To do so I took a rectangular region whose side is the double of the tolerance accumulating points as long as the rectangle could contain all of them. At this point I started with another rectangle containing at least the last point of the former rectangle.
