On a Problem of Danzer

Let C be a bounded convex object in R' ^d , and let P be a set of n points lying outside C. Further, let cp, cq be two integers with 1 ≤ cq ≤ cp ≤ n - d/2, such that every cp + d/2 points of P contain a subset of size cq + d/2 whose convex hull is disjoint from C. Then our main theorem states the existence of a partition of P into a small number of subsets, each of whose convex hulls are disjoint from C. Our proof is constructive and implies that such a partition can be computed in polynomial time. In particular, our general theorem implies polynomial bounds for Hadwiger - Debrunner (p, q) numbers for balls in R' ^d . For example, it follows from our theorem that when p > q = (1+β).d/2 for β > 0, then any set of balls satisfying the (p, q)-property can be hit by O((1+β) ² d ² p ^1+1/β logp) points. This is the first improvement over a nearly 60 year-old exponential bound of roughly O(2 ^d ). Our results also complement the results obtained in a recent work of Keller, Smorodinsky and Tardos where, apart from improvements to the bound on HD(p, q) for convex sets in R' ^d for various ranges of p and q, a polynomial bound is obtained for regions with low union complexity in the plane.