# 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?

-
Just my first thought: how can you finish your computation without some a priori information on the number of affine pieces? It seems this problem is actually two different problems, the first of which is not too well posed, namely 1) find a point in each affine component, and 2) compute the extent and slopes of each component –  Piero D'Ancona Aug 31 '10 at 15:35