Approximation Depth of Convex Polytopes

2025/07/10 by Egor Bakaev, Florestan Brunck, Bakaev, Egor +3
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Metric Geometry (math.MG) #Point processes and geometric inequalities #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.2507.07779

openalex publication_date 2025/07/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study approximations of polytopes in the standard model for computing polytopes using Minkowski sums and (convex hulls of) unions. Specifically, we study the ability to approximate a target polytope by polytopes of a given depth. Our main results imply that simplices can only be ``trivially approximated''. On the way, we obtain a characterization of simplices as the only ``outer additive'' convex bodies.

Citations

• On the Depth of Monotone ReLU Neural Networks and ICNNs
• On Minimal Depth in Neural Networks
• Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes
• Size and depth of monotone neural networks: interpolation and approximation
• Counterexample-Guided Learning of Monotonic Neural Networks
• Monotone and Partially Monotone Neural Networks
• Containment and inscribed simplices

Related

• On approximations by projections of polytopes with few facets
• Tight Bounds for Approximate Carathéodory and Beyond
• Flag-approximability of convex bodies and volume growth of Hilbert geometries
• Optimal Volume-Sensitive Bounds for Polytope Approximation
• On the approximation of a polytope by its dual L_p-centroid bodies