Bounds on the Number of Pieces in Continuous Piecewise Affine Functions

2025/03/12 by Zanotti, Leo · 1 citation
Mathematics · #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Approximation and Integration #Point processes and geometric inequalities

paper · pdf · doi:10.48550/arxiv.2503.09525

openalex publication_date 2025/03/12 · openalex created_date 2025/10/13 · openalex updated_date 2026/07/28

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 ℝ^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=Ω(n^{d+1-(c)/(√(log₂(n)))}).

Cited by

• The Computational Complexity of Counting Linear Regions in ReLU Neural Networks

Related

• Representing Piecewise-Linear Functions by Functions with Minimal Arity
• Finding the set of global minimizers of a piecewise affine function
• An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean Function
• Error Bounds for Compositions of Piecewise Affine Approximations
• Locally piecewise affine functions and their order structure