This work focuses on the approximation of bivariate functions into piecewise linear ones with a minimal number of pieces and under a bounded approximation error. Applications include the approximation of mixed integer nonlinear optimization problems into mixed integer linear ones that are in general easier to solve. A framework to build dedicated linearization algorithms is introduced, and a comparison to the state of the art heuristics shows their efficiency.