Improved upper bounds for approximation by zonotopes

DOI10.1007/BF02392598zbMath0887.52003MaRDI QIDQ1373005

Ji{ří} Matoušek

Publication date: 5 November 1997

Published in: Acta Mathematica (Search for Journal in Brave)

zbMATH Keywords

approximationzonotopezonoidpolynomial-time deterministic algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Approximation by convex sets (52A27)

Related Items (4)

Uniform approximation rates and metric entropy of shallow neural networks ⋮ Isoperimetric problems for zonotopes ⋮ Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique ⋮ Convergence of algorithms for reconstructing convex bodies and directional measures

Cites Work

• Unnamed Item
• Unnamed Item
• A deterministic view of random sampling and its use in geometry
• Distribution of points on spheres and approximation by zonotopes
• Cutting hyperplane arrangements
• Efficient partition trees
• On a new method for constructing good point sets on spheres
• Approximating the ball by a Minkowski sum of segments with equal length
• Cutting hyperplanes for divide-and-conquer
• Quasi-optimal range searching in spaces of finite VC-dimension
• Approximation of zonoids by zonotopes
• Approximation of a ball by zonotopes using uniform distribution on the sphere
• Tight upper bounds for the discrepancy of half-spaces
• Some upper bounds in the theory of irregularities of distribution
• Six Standard Deviations Suffice
• Discrepancy in arithmetic progressions

This page was built for publication: Improved upper bounds for approximation by zonotopes