### Abstract

Let C be a bounded convex object in R^{d}, and P a set of n points lying outside C. Further let c_{p}, c_{q} be two integers with 1 ≤ c_{q} η c_{p} ≤ n - ⌊d/2⌋, such that every c_{p} + ⌊d/2⌋ points of P contains a subset of size c_{q} + ⌊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-hull is 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 ℝ^{d}. For example, it follows from our theorem that when p > q ≥ (1 + β) · d/2 for β > 0, then any set of balls satisfying the HD(p, q) property can be hit by O (q^{2}p^{1}+1/β logp p) 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 et al. where, apart from improvements to the bound on HD(p, q) for convex sets in ℝ^{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) |
---|---|

Title of host publication | 26th European Symposium on Algorithms, ESA 2018 |

Editors | Hannah Bast, Grzegorz Herman, Yossi Azar |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Print) | 9783959770811 |

DOIs | |

State | Published - Aug 1 2018 |

Event | 26th European Symposium on Algorithms, ESA 2018 - Helsinki, Finland Duration: Aug 20 2018 → Aug 22 2018 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 112 |

ISSN (Print) | 1868-8969 |

### Other

Other | 26th European Symposium on Algorithms, ESA 2018 |
---|---|

Country | Finland |

City | Helsinki |

Period | 8/20/18 → 8/22/18 |

### Keywords

- Balls
- Convex polytopes
- Epsilon-nets
- Hadwiger-Debrunner numbers

### ASJC Scopus subject areas

- Software

## Fingerprint Dive into the research topics of 'On a problem of danzer'. Together they form a unique fingerprint.

## Cite this

*26th European Symposium on Algorithms, ESA 2018*(Leibniz International Proceedings in Informatics, LIPIcs; Vol. 112). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ESA.2018.64