## Abstract

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+β) ^{2} d ^{2} 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.

Original language | English (US) |
---|---|

Pages (from-to) | 473-482 |

Number of pages | 10 |

Journal | Combinatorics Probability and Computing |

Volume | 28 |

Issue number | 3 |

DOIs | |

State | Published - May 1 2019 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics