Bounds on the Number of Pieces in Continuous Piecewise Affine Functions

Abstract

The complexity of continuous piecewise affine (CPA) functions can be measured by the number of pieces $p$ or the number of distinct affine functions $n$. For CPA functions on ${\mathbb{R}}^d$, this paper shows an upper bound of $p=O(n^{d+1})$ and constructs a family of functions achieving a lower bound of $p=\Omega (n^{d+1-\frac{c}{\sqrt{{\log }_2(n)}}})$.