Representing Piecewise-Linear Functions by Functions with Minimal Arity

Any continuous piecewise-linear function F\colon \mathbb{R}^{n}\to \mathbb{R} can be represented as a linear combination of \max functions of at most n+1 affine-linear functions. In our previous paper [``Representing piecewise linear functions by functions with small arity'', AAECC, 2023], we showed that this upper bound of n+1 arguments is tight. In the present paper, we extend this result by establishing a correspondence between the function F and the minimal number of arguments that are needed in any such decomposition. We show that the tessellation of the input space \mathbb{R}^{n} induced by the function F has a direct connection to the number of arguments in the \max functions.