TY - GEN
T1 - On a problem of danzer
AU - Mustafa, Nabil H.
AU - Ray, Saurabh
N1 - Funding Information:
The work of Nabil H. Mustafa in this paper has been supported by the grant ANR SAGA (JCJC-14-CE25-0016-01).
Publisher Copyright:
© Nabil H. Mustafa and Saurabh Ray.
PY - 2018/8/1
Y1 - 2018/8/1
N2 - Let C be a bounded convex object in Rd, and P 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 contains 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-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 (q2p1+1/β logp p) points. This is the first improvement over a nearly 60-year old exponential bound of roughly O(2d). 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.
AB - Let C be a bounded convex object in Rd, and P 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 contains 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-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 (q2p1+1/β logp p) points. This is the first improvement over a nearly 60-year old exponential bound of roughly O(2d). 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.
KW - Balls
KW - Convex polytopes
KW - Epsilon-nets
KW - Hadwiger-Debrunner numbers
UR - http://www.scopus.com/inward/record.url?scp=85052516253&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85052516253&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ESA.2018.64
DO - 10.4230/LIPIcs.ESA.2018.64
M3 - Conference contribution
AN - SCOPUS:85052516253
SN - 9783959770811
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 26th European Symposium on Algorithms, ESA 2018
A2 - Bast, Hannah
A2 - Herman, Grzegorz
A2 - Azar, Yossi
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 26th European Symposium on Algorithms, ESA 2018
Y2 - 20 August 2018 through 22 August 2018
ER -