×

Positive-fraction intersection results and variations of weak epsilon-nets. (English) Zbl 1456.52009

Summary: Given a finite set \(X\) of points in \(R^n\) and a family \(F\) of sets generated by the pairs of points of \(X\), we determine volumetric and structural conditions for the sets that allow us to guarantee the existence of a positive-fraction subfamily \(F^\prime\) of \(F\) for which the sets have non-empty intersection. This allows us to show the existence of weak epsilon-nets for these families. We also prove a topological variation of the existence of weak epsilon-nets for convex sets.

MSC:

52A35 Helly-type theorems and geometric transversal theory
52A30 Variants of convex sets (star-shaped, (\(m, n\))-convex, etc.)
52A38 Length, area, volume and convex sets (aspects of convex geometry)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon, N., Bárány, I., Füredi, Z., Kleitman, D.J.: Point selections and weak \[\varepsilon\] ε-nets for convex hulls. Combin. Probab. Comput. 1(03), 189-200 (1992) · Zbl 0797.52004 · doi:10.1017/S0963548300000225
[2] Bárány, I.: A generalization of Carathéodory’s theorem. Discrete Math. 40(2-3), 141-152 (1982) · Zbl 0492.52005 · doi:10.1016/0012-365X(82)90115-7
[3] Bárány, I.: An extension of the Erdős-Szekeres theorem on large angles. Combinatorica 7(2), 161-169 (1987) · Zbl 0655.51007 · doi:10.1007/BF02579447
[4] Bárány, I., Füredi, Z.: Computing the volume is difficult. Discrete Comput. Geom. 2(1), 319-326 (1987) · Zbl 0628.68041 · doi:10.1007/BF02187886
[5] Bárány, I., Lehel, J.: Covering with Euclidean boxes. Eur. J. Combin. 8(2), 113-119 (1987) · Zbl 0623.05041 · doi:10.1016/S0195-6698(87)80001-X
[6] Bárány, I., Shlosman, S.B., Szücs, A.: On a topological generalization of a theorem of Tverberg. J. Lond. Math. Soc. 2(1), 158-164 (1981) · Zbl 0453.55003 · doi:10.1112/jlms/s2-23.1.158
[7] Boros, E., Füredi, Z.: The number of triangles covering the center of an n-set. Geom. Dedicata 17(1), 69-77 (1984) · Zbl 0595.52002 · doi:10.1007/BF00181519
[8] Bukh, B.: A point in many triangles. Electron. J. Combin. 13(1), Note 10, 3 pp (2006) · Zbl 1165.52301
[9] Bukh, B., Matoušek, J., Nivasch, G.: Stabbing simplices by points and flats. Discrete Comput. Geom. 43(2), 321-338 (2010) · Zbl 1186.52001 · doi:10.1007/s00454-008-9124-4
[10] Bukh, B., Matoušek, J., Nivasch, G.: Lower bounds for weak epsilon-nets and stair-convexity. Isr. J. Math. 182(1), 199-228 (2011) · Zbl 1222.68395 · doi:10.1007/s11856-011-0029-1
[11] Chazelle, B., Edelsbrunner, H., Grigni, M., Guibas, L., Sharir, M., Welzl, E.: Improved bounds on weak \[\varepsilon\] ε-nets for convex sets. Discrete Comput. Geom. 13(1), 1-15 (1995) · Zbl 0822.68110 · doi:10.1007/BF02574025
[12] Fox, J., Gromov, M., Lafforgue, V., Naor, A., Pach, J.: Overlap properties of geometric expanders. J. Reine Angew. Math. 671, 49-83 (2012) · Zbl 1306.05171
[13] Gromov, M.: Singularities, expanders and topology of maps. Part 2: from combinatorics to topology via algebraic isoperimetry. Geom. Funct. Anal. 20(2), 416-526 (2010) · Zbl 1251.05039 · doi:10.1007/s00039-010-0073-8
[14] Jiang, Z.: A slight improvement to the colored bárány’s theorem. Electron. J. Combin. 21(4), 1-8 (2014) · Zbl 1305.05033
[15] Karasev, R.N.: A simpler proof of the Boros-Füredi-Bárány-Pach-Gromov theorem. Discrete Comput. Geom. 47(3), 492-495 (2012) · Zbl 1237.05054 · doi:10.1007/s00454-011-9332-1
[16] Katchalski, M., Liu, A.: A problem of geometry in \[R^nRn\]. Proc. Am. Math. Soc. 75(2), 284-288 (1979) · Zbl 0418.52013
[17] Král, D., Mach, L., Sereni, J.-S.: A new lower bound based on Gromov’s method of selecting heavily covered points. Discrete Comput. Geom. 48(2), 487-498 (2012) · Zbl 1262.05151 · doi:10.1007/s00454-012-9419-3
[18] Matoušek, J.: Using the Borsuk-Ulam Theorem. Universitext. Lectures on topological methods in combinatorics and geometry. Springer, Berlin (2003). Written in cooperation with Anders Björner and Günter M. Ziegler · Zbl 1016.05001
[19] Matoušek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer, New York (2002) · Zbl 0999.52006
[20] Matoušek, J., Wagner, U.: New constructions of weak epsilon-nets. Discrete Comput. Geom. 32(2), 195-206 (2004) · Zbl 1104.68124
[21] Matoušek, J., Wagner, U.: On Gromov’s method of selecting heavily covered points. Discrete Comput. Geom. 52(1), 1-33 (2014) · Zbl 1298.51027 · doi:10.1007/s00454-014-9584-7
[22] Pach, J.: A Tverberg-type result on multicolored simplices. Comput. Geom. 10(2), 169-178 (1998) · Zbl 0896.68143
[23] Rado, R.: A theorem on general measure. J. Lond. Math. Soc. 21, 291-300 (1946) · Zbl 0061.09606 · doi:10.1112/jlms/s1-21.4.291
[24] Rolnick, D., Soberón, P.: Quantitative \[(p, q)\](p,q) theorems in combinatorial geometry (2015). arXiv:1504.01642 [math.MG] · Zbl 1379.52007
[25] Tverberg, H.: A generalization of Radon’s theorem. J. Lond. Math. Soc 41(1), 123-128 (1966) · Zbl 0131.20002 · doi:10.1112/jlms/s1-41.1.123
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.