Quantitative Helly-type theorems via sparse approximation
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' satisfies Q subset of -2d(2) Q'. As a consequence, we retrieve the best bound for the quantitative Helly-typ...
Elmentve itt :
| Szerzők: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
2023
|
| Sorozat: | DISCRETE AND COMPUTATIONAL GEOMETRY
70 No. 4 |
| Tárgyszavak: | |
| doi: | 10.1007/s00454-022-00441-5 |
| mtmt: | 32257228 |
| Online Access: | http://publicatio.bibl.u-szeged.hu/29682 |
| Tartalmi kivonat: | 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' satisfies Q subset of -2d(2) Q'. 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 Naszodi: We prove that given a finite family F of convex bodies in R-d with intersection K, we may select at most 2d members of F such that their intersection has volume at most (cd)(3d)(/2) vol K, and it has diameter at most 2d(2) diam K, for some absolute constant c > 0. |
|---|---|
| Terjedelem/Fizikai jellemzők: | 1707-1714 |
| ISSN: | 0179-5376 |