The upper envelope of piecewise linear functions: Tight bounds on the number of faces (Q919829)

A proof of combinatorial complexity of the upper envelope of piecewise linear functions is given. The upper envelope of the system of functions is defined as a pointwise maximum of functions of this system. In the case of piecewise linear functions the envelope form a cell complex. The cardinality of all faces of this complex is called a combinatorial complexity of the envelope. It is shown that in the worst case the complexity of the envelope is \(\theta (n^ d\alpha (n))\), where \(\alpha\) (n) is the inverse Ackermann's function and n is the number of linear parts of the function. The proof of this result is based on divide-and- conquer method.