×

On a problem of Danzer. (English) Zbl 1436.52020

Summary: Let \(C\) be a bounded convex object in \(\mathbb{R}^d\), and let \(P\) be a set of \(n\) points lying outside \(C\). Further, let \(c_p, c_q\) be two integers with \(1 \leqslant c_q \leqslant c_p \leqslant n - \lfloor d/2 \rfloor\), such that every \(c_p + \lfloor d/2 \rfloor\) points of \(P\) contain a subset of size \(c_q + \lfloor d/2 \rfloor\) 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 \(\mathbb{R}^d \). For example, it follows from our theorem that when \(p > q = (1+ \beta)\cdot d/2\) for \(\beta > 0\), then any set of balls satisfying the \((p, q)\)-property can be hit by \(O((1+\beta)^2 d^2 p^{1+1/ \beta} \operatorname{log} 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, Smorodinsky and Tardos where, apart from improvements to the bound on HD \((p, q)\) for convex sets in \(\mathbb{R}^d\) for various ranges of \(p\) and \(q\), a polynomial bound is obtained for regions with low union complexity in the plane.

MSC:

52C45 Combinatorial complexity of geometric structures
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N. and Kleitman, D. (1992) Piercing convex sets and the Hadwiger-Debrunner (p, q)-problem.Adv. Math.96103-112. · Zbl 0768.52001
[2] Bourgain, J. and Lindenstrauss, J. (1991) On covering a set in R^n by balls of the same diameter. In Geometric Aspects of Functional Analysis, Springer, pp. 138-144. · Zbl 0815.46017
[3] De Caen, D. (1983) Extension of a theorem of Moon and Moser on complete subgraphs.Ars Combin.165-10. · Zbl 0532.05037
[4] Clarkson, K. and Shor, P. (1989) Applications of random sampling in computational geometry, II.Discrete Comput. Geom.4387-421. · Zbl 0681.68060
[5] Danzer, L. (1960) Über zwei Lagerungsprobleme: Abwandlungen einer Vermutung von T. Gallai. PhD thesis, Technische Hochschule München.
[6] Danzer, L. (1961) Über Durchschnittseigenschaften n-dimensionaler Kugelfamilien.J. Reine Angew. Math.208181-203. · Zbl 0109.14904
[7] Eckhoff, J. (2003) A survey of the Hadwiger-Debrunner (p, q)-problem. In Discrete and Computational Geometry: The Goodman-Pollack Festschrift (Aronov, B.et al., eds), Springer, pp. 347-377. · Zbl 1084.52002
[8] Holmsen, A. and Wenger, R. (2017) Helly-type theorems and geometric transversals. In Handbook of Discrete and Computational Geometry (Goodman, J. E.et al., eds), CRC Press, pp. 91-123.
[9] Keller, C., Smorodinsky, S. and Tardos, G. (2017) On Max-Clique for intersection graphs of sets and the Hadwiger-Debrunner numbers. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2254-2263. · Zbl 1417.52007
[10] Keller, C., Smorodinsky, S. and Tardos, G. (2018) Improved bounds on the Hadwiger-Debrunner numbers.Israel J. Math.225925-945. · Zbl 1390.05235
[11] Kupavskii, A., Mustafa, N. H. and Pach, J. (2017) Near-optimal lower bounds for ε-nets for half-spaces and low complexity set systems. In A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek (Loebl, M.et al., eds), Springer, pp. 527-541. · Zbl 1425.68434
[12] Matoušek, J. (2002) Lectures in Discrete Geometry, Springer. · Zbl 0999.52006
[13] Mustafa, N. H., Dutta, K. and Ghosh, A. (2017) A simple proof of optimal epsilon-nets. Combinatorica doi: doi:10.1007/s00493-017-3564-5 · Zbl 1424.52020
[14] Mustafa, N. H. and Ray, S. (2008) Weak ε-nets have basis of size O(1/εlog(1/ε)) in any dimension.Comput. Geom. Theory Appl.4084-91. · Zbl 1135.68054
[15] Mustafa, N. H. and Ray, S. (2016) An optimal generalization of the colorful Carathéodory theorem.Discrete Math.3391300-1305. · Zbl 1333.52005
[16] Mustafa, N. H. and Varadarajan, K. (2017) Epsilon-approximations and epsilon-nets. In Handbook of Discrete and Computational Geometry (Goodman, J. E.et al., eds), CRC Press, pp. 1241-1268.
[17] Smorodinsky, S., Sulovský, M. and Wagner, U. (2008) On center regions and balls containing many points. In Proceedings of the 14th Annual International Conference on Computing and Combinatorics (COCOON’08) (Hu, X. and Wang, J., eds), Springer, pp. 363-373. · Zbl 1148.68554
[18] Wagner, U. (2008) k-sets and k-facets. In Surveys on Discrete and Computational Geometry: Twenty Years Later (Goodman, J.et al., eds), Contemporary Mathematics, American Mathematical Society, pp. 231-255. · Zbl 1149.52012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.