geometry - Recovering a piecewise affine function

Lets say I have an piecewise affine convex function $f(x_1,x_2)$, on which the following operations are possible:

• Computing $f(x_1,x_2)$.


• Computing a subgradient to $f$ at $(x_1,x_2)$


• Computing all breakpoints along a line $a_1x_1 + a_2x_2 = a_3$

What is an efficient algorithm to compute $f$ completely, i.e. to compute all its breakpoints? Are there any general methods?

• Next Algebraic (semi-) Riemannian geometry ?
• Previous co.combinatorics - What exactly is the relationship between codes over finite fields and Euclidean sphere-packings?