Piecewise linear approximation for set of points If we have a set of points $A$ and a known algorithm $Bestfit(A)$ to find
the best-fit straight line-segment through $A$, what would be a good algorithm to construct piece-wise linear segments (with at most $k$ segments) to give a better approximate of the set of points and reduce the error $E$?
This can be solved with a straightforward dynamic programming algorithm.  If you have $n$ data points, it can be solved in $O(n^2)$ calls to BestFit plus $O(n^2 k)$ time.  See https://cs.stackexchange.com/tags/dynamic-programming/info for our resources on how to construct dynamic programming algorithms.