Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-24T12:53:24.205Z Has data issue: false hasContentIssue false
  • English
  • Français

On a Problem of Danzer

Part of: Discrete geometry

Published online by Cambridge University Press:  15 October 2018

NABIL H. MUSTAFA  and
SAURABH RAY
NABIL H. MUSTAFA
Affiliation:
Université Paris-Est, Laboratoire d'Informatique Gaspard-Monge, Equipe A3SI, ESIEE Paris, France (e-mail: [email protected])
SAURABH RAY
Affiliation:
Computer Science, New York University, Abu Dhabi, United Arab Emirates (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Let C be a bounded convex object in ℝ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 ℝ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+β)2d2p1+1/β logp) 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, Smorodinsky and Tardos 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.

MSC classification

Primary: 52C45: Combinatorial complexity of geometric structures
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 28 , Issue 3 , May 2019 , pp. 473 - 482
Copyright
Copyright © Cambridge University Press 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†The conference version of this paper appeared in the 26th Annual European Symposium on Algorithms, 2018.

‡

The work of Nabil H. Mustafa in this paper was supported by the grant ANR SAGA (JCJC-14-CE25-0016-01).

References

[1] Alon, N. and Kleitman, D. (1992) Piercing convex sets and the Hadwiger–Debrunner (p, q)-problem. Adv. Math. 96 103–112.Google Scholar
[2] Bourgain, J. and Lindenstrauss, J. (1991) On covering a set in Rn by balls of the same diameter. In Geometric Aspects of Functional Analysis, Springer, pp. 138–144.Google Scholar
[3] de Caen, D. (1983) Extension of a theorem of Moon and Moser on complete subgraphs. Ars Combin. 16 5–10.Google Scholar
[4] Clarkson, K. and Shor, P. (1989) Applications of random sampling in computational geometry, II. Discrete Comput. Geom. 4 387–421.Google Scholar
[5] Danzer, L. (1960) Über zwei Lagerungsprobleme: Abwandlungen einer Vermutung von T. Gallai. PhD thesis, Technische Hochschule München.Google Scholar
[6] Danzer, L. (1961) Über Durchschnittseigenschaften n-dimensionaler Kugelfamilien. J. Reine Angew. Math. 208 181–203.Google Scholar
[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.Google Scholar
[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.Google Scholar
[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.Google Scholar
[10] Keller, C., Smorodinsky, S. and Tardos, G. (2018) Improved bounds on the Hadwiger–Debrunner numbers. Israel J. Math. 225 925–945.Google Scholar
[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.Google Scholar
[12] Matoušek, J. (2002) Lectures in Discrete Geometry, Springer.Google Scholar
[13] Mustafa, N. H., Dutta, K. and Ghosh, A. (2017) A simple proof of optimal epsilon-nets. Combinatorica doi:10.1007/s00493-017-3564-5Google Scholar
[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. 40 84–91.Google Scholar
[15] Mustafa, N. H. and Ray, S. (2016) An optimal generalization of the colorful Carathéodory theorem. Discrete Math. 339 1300–1305.Google Scholar
[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.Google Scholar
[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.Google Scholar
[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.Google Scholar