Quantitative combinatorial geometry for concave functions

Abstract

We prove several exact quantitative versions of Helly's and Tverberg's theorems, which guarantee that a finite family of convex sets in $R^d$ has a large intersection. Our results characterize conditions that are sufficient for the intersection of a family of convex sets to contain a "witness set" which is large under some concave or log-concave measure. The possible witness sets include ellipsoids, zonotopes, and $H$-convex sets. Our results also bound the complexity of finding the best approximation of a family of convex sets by a single zonotope or by a single $H$-convex set. We obtain colorful and fractional variants of all our Helly-type theorems.

25 pages, 2 figures