Algorithm for best piecewise linear fit Suppose your are given a finite set $P$ of $n$ points $(x_i,y_i)$ with  $x_0< x_1 <\ldots < x_n$.
Denote by $f_P$ the function given by piecewise linear joining of these points.
Now suppose you are given $k<n$. I feel the following problem must have a well known algorithmic solution,
but I am unable to use the right keywords to find it.
Given $k$, find a subset $S \subseteq P$ containing the endpoints with $|S|=k$, such that $f_S$ is the best fit to $f_P$
in eithter L1 or L2 sense i.e. such that
$$\int_{x_0}^{x_n} |f_P(x)-f_S(x)| dx $$
or
$$ \int_{x_0}^{x_n} (f_P(x)-f_S(x))^2 dx $$
is minimal.
How are these optimization problems called? Are there fast algorithms.
Does it help if you knew that $f_P$ had special properties. E.g. monotone or convex?
Let me add that in the application I have in mind $k$ is rather small compared to $n$, maybe something like 10  to 10000.

They are called Piecewise Affine Approximations.  In general the problem is non-convex, one problem formulation is something like
\begin{equation}
\begin{array}{rcl}
J&=&\sum_{i=1}^n \int_{S_i} |f(x)-L_i(x)|^2 dx\label{20130516:eq1}\\
\text{such that } \bigcup_{i=1}^n S_i&=&I \text{ and } \bigcap_{any\ two} S_i=\emptyset.\nonumber\\
L_i(x)&=&\frac{df}{dx}(x_i^*)(x-x_i^*)+f(x_i^*).
\end{array}
\end{equation}
I do not know of fast analytic algorithms, I typically discretize and use constrained least squares.  One resource to get you started is Optimal Piecewise Affine Approximations of Nonlinear Functions Obtained from Measurements by Szucs, Kvasnica, and Fiskar.
