Quantitative Helly-type theorems via sparse approximation

DOI10.1007/S00454-022-00441-5MaRDI QIDQ6142362zbMATH OpenOpenAlexWikidataFDO

Authors Víctor Hugo Almendra-Hernández, Gergely Ambrus, Matthew Kendall

Publication date 21 December 2023

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2108.05745, http://real.mtak.hu/131747/2/32234.pdf

zbMATH Keywords

volumesparse approximationdiameterJohn's ellipsoidHelly-type theorem

Mathematics Subject Classification ID

Length, area, volume and convex sets (aspects of convex geometry) (52A38) Approximation by convex sets (52A27) Helly-type theorems and geometric transversal theory (52A35)

Abstract: We prove the following sparse approximation result for polytopes. Assume that $Q$ is a polytope in John's position. Then there exist at most $2d$ vertices of $Q$ whose convex hull $Q^{\prime }$ satisfies $Qsubseteq-2d^2,Q^{\prime }$. As a consequence, we retrieve the best bound for the quantitative Helly-type result for the volume, achieved by Brazitikos, and improve on the strongest bound for the quantitative Helly-type theorem for the diameter, shown by Ivanov and Nasz'odi: We prove that given a finite family $mathcalF$ of convex bodies in $mathbb{R}^d$ with intersection $K$, we may select at most $2d$ members of $mathcalF$ such that their intersection has volume at most $(cd{)}^{3d/2},mathrmvol,K$, and it has diameter at most $2d^2,mathrmdiam,K$, for some absolute constant $c>0$.

Recommendations

• A quantitative Helly-type theorem: containment in a homothet
• Continuous quantitative Helly-type results
• Quantitative Helly-type theorem for the diameter of convex sets
• Quantitative fractional Helly and \((p,q)\)-theorems
• Brascamp-Lieb inequality and quantitative versions of Helly's theorem

Cites work

• scientific article; zbMATH DE number 1149836 (Why is no real title available?)
• scientific article; zbMATH DE number 3052220 (Why is no real title available?)
• A mélange of diameter Helly-type theorems
• A quantitative Helly-type theorem: containment in a homothet
• Absolute and Unconditional Convergence in Normed Linear Spaces
• Asymptotic geometric analysis. I
• Brascamp-Lieb inequality and quantitative versions of Helly's theorem
• Continuous quantitative Helly-type results
• Functional John ellipsoids
• Helly's Theorem with Volumes
• Helly-type problems
• John's decomposition in the general case and applications
• Polynomial esimates towards a sharp Helly-type theorem for the diameter of convex sets
• Proof of a conjecture of Bárány, Katchalski and Pach
• Quantitative Helly-Type Theorems
• Quantitative Helly-type theorem for the diameter of convex sets

Cited in

(4)

• Quantitative Steinitz theorem: A polynomial bound
• Colorful positive bases decomposition and Helly-type results for cones
• Helly numbers for quantitative Helly-type results
• Sparse approximation of triangular transports. II: The infinite-dimensional case

This page was built for publication: Quantitative Helly-type theorems via sparse approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6142362)