Re: Complexity of piecewise linear functions

Francis Sourd wrote:

> Let f, g be two (continuous) piecewise linear functions and let OP be an
> operator on f and g that returns a piecewise linear function. The problem is
> to estimate the number of segments of OP(f,g).
>
> For example,
> f+g has at most |f|+|g| segments (|f| is the number of segments of f)
> min(f,g) has at most 2(|f|+|g|) segments.
>
> There are more difficult problems. For example
> t -> min_{t=t1+t2} f(t1)+g(t2)
> may have at least |f||g| segments.
>
> Do you know any survey? general results? study for special OP?
> Any reference or pointer is welcome.

If I understand your three examples, it seems you can
make the number of segments as large as you want:
Pick n, a_i, b_i, i=1..n and form min_i{f(a_i x) + g(b_i x)}.
(You will obviously need some conditions on the a_i, b_i,
but I am too lazy to put any more work into it.)