Helly’s theorem: new variations and applications. (English) Zbl 1383.52006
Harrington, Heather A. (ed.) et al., Algebraic and geometric methods in discrete mathematics. AMS special session on algebraic and geometric methods in applied discrete mathematics, San Antonio, TX, USA, January 11, 2015. Proceedings. Providence, RI: American Mathematical Society (AMS) (ISBN 978-1-4704-2321-6/pbk; 978-1-4704-3743-5/ebook). Contemporary Mathematics 685, 55-95 (2017).
This paper is an extensive survey on the Helly theorem and related results. The Helly theorem is a classical result in discrete geometry and it states the following: if we are given a finite collection of at least \(d+1\) convex sets in \(\mathbb{R}^d\) such that the intersection of every \((d+1)\)-tuple of sets in the collection is nonempty, then the intersection of all sets in the collection is nonempty. This innocent-looking theorem has a plethora of generalizations, variants, or counterparts, as well as interesting applications (for example in optimization).
The task of the survey is to describe the (mostly) recent development of the results related to Helly theorem, mostly considering the geometric setting. In particular, the survey includes (quite exhaustive) description of the following topics.
For the entire collection see [Zbl 1362.00040].
The task of the survey is to describe the (mostly) recent development of the results related to Helly theorem, mostly considering the geometric setting. In particular, the survey includes (quite exhaustive) description of the following topics.
- \(\bullet\)
- Helly-type theorems where the intersection is considered in a prescribed set.
- \(\bullet\)
- Colorful versions. (The sets are colored and the intersection condition is related to the coloring.)
- \(\bullet\)
- Quantitative versions. (The intersection is supposed to be large in some sense.)
- \(\bullet\)
- Topological versions. (The convexity condition is relaxed to a weaker topological condition.)
- \(\bullet\)
- Fractional versions. (Only a fraction of intersections is assumed to be nonempty with conclusion that a fraction of the sets has nonempty intersection.)
- \(\bullet\)
- \((p,q)\) versions. (For \(p \geq q\), if among every \(p\) sets there are \(q\) sets with non-empty intersections, deduce that all sets can be hit by a bounded number of points.)
- \(\bullet\)
- Transversal theorems. (Nonempty intersection is replaced with existence of transversal line, affine space, etc.)
- \(\bullet\)
- Applications of Helly-type theorems in optimization (and vice versa).
For the entire collection see [Zbl 1362.00040].
Reviewer: Martin Tancer (Praha)
MSC:
| 52A35 | Helly-type theorems and geometric transversal theory |
References:
| [1] | Arocha, Jorge L.; Bracho, Javier, A Helly type theorem for abstract projective geometries, Discrete Comput. Geom., 45, 2, 223-229 (2011) · Zbl 1211.52007 · doi:10.1007/s00454-010-9287-7 |
| [2] | Arocha, Jorge L.; B{\'a}r{\'a}ny, Imre; Bracho, Javier; Fabila, Ruy; Montejano, Luis, Very colorful theorems, Discrete Comput. Geom., 42, 2, 142-154 (2009) · Zbl 1173.52002 · doi:10.1007/s00454-009-9180-4 |
| [3] | I. Aliev, R. Bassett, J. A. De Loera, and Q. Louveaux, A Quantitative Doignon-Bell-Scarf Theorem, to appear in Combinatorica, preprint available in Math ArXiv 1405.2480v1. · Zbl 1399.52011 |
| [4] | Ambrus, G.; Bezdek, A.; Fodor, F., A Helly-type transversal theorem for \(n\)-dimensional unit balls, Arch. Math. (Basel), 86, 5, 470-480 (2006) · Zbl 1096.52005 · doi:10.1007/s00013-005-1446-3 |
| [5] | Alon, Noga; B{\'a}r{\'a}ny, Imre; F{\`“u}redi, Zolt{\'”a}n; Kleitman, Daniel J., Point selections and weak \(\epsilon \)-nets for convex hulls, Combin. Probab. Comput., 1, 3, 189-200 (1992) · Zbl 0797.52004 · doi:10.1017/S0963548300000225 |
| [6] | Arocha, Jorge L.; Bracho, Javier; Montejano, Luis, A colorful theorem on transversal lines to plane convex sets, Combinatorica, 28, 4, 379-384 (2008) · Zbl 1164.52003 · doi:10.1007/s00493-008-2385-y |
| [7] | Alon, Noga; Kleitman, Daniel J., Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem, Adv. Math., 96, 1, 103-112 (1992) · Zbl 0768.52001 · doi:10.1016/0001-8708(92)90052-M |
| [8] | Alon, N.; Kalai, G., Bounding the piercing number, Discrete Comput. Geom., 13, 3-4, 245-256 (1995) · Zbl 0826.52006 · doi:10.1007/BF02574042 |
| [9] | Alon, N.; Kleitman, D. J., A purely combinatorial proof of the Hadwiger Debrunner \((p,q)\) conjecture, Electron. J. Combin., 4, 2, Research Paper 1, approx. 8 pp. (electronic) pp. (1997) · Zbl 0889.52008 |
| [10] | Alon, Noga; Kalai, Gil; Matou{\v{s}}ek, Ji{\v{r}}{\'{\i }}; Meshulam, Roy, Transversal numbers for hypergraphs arising in geometry, Adv. in Appl. Math., 29, 1, 79-101 (2002) · Zbl 1027.52003 · doi:10.1016/S0196-8858(02)00003-9 |
| [11] | Andersen, Kent; Louveaux, Quentin; Weismantel, Robert, An analysis of mixed integer linear sets based on lattice point free convex sets, Math. Oper. Res., 35, 1, 233-256 (2010) · Zbl 1220.90070 · doi:10.1287/moor.1090.0439 |
| [12] | N. Amenta, Bounded boxes, Hausdorff distance, and a new proof of an interesting helly-type theorem, Proceedings of the tenth annual symposium on Computational geometry, ACM, 1994, pp. 340-347. |
| [13] | Amenta, N., Helly-type theorems and generalized linear programming, Discrete Comput. Geom., 12, 3, 241-261 (1994) · Zbl 0819.90056 · doi:10.1007/BF02574379 |
| [14] | Amenta, N., A short proof of an interesting Helly-type theorem, Discrete Comput. Geom., 15, 4, 423-427 (1996) · Zbl 0851.52007 · doi:10.1007/BF02711517 |
| [15] | Alon, Noga; Pach, J{\'a}nos; Pinchasi, Rom; Radoi{\v{c}}i{\'c}, Rado{\v{s}}; Sharir, Micha, Crossing patterns of semi-algebraic sets, J. Combin. Theory Ser. A, 111, 2, 310-326 (2005) · Zbl 1099.14048 · doi:10.1016/j.jcta.2004.12.008 |
| [16] | Averkov, Gennadiy, On maximal \(S\)-free sets and the Helly number for the family of \(S\)-convex sets, SIAM J. Discrete Math., 27, 3, 1610-1624 (2013) · Zbl 1282.90109 · doi:10.1137/110850463 |
| [17] | Averkov, Gennadiy, A proof of Lov\'asz’s theorem on maximal lattice-free sets, Beitr. Algebra Geom., 54, 1, 105-109 (2013) · Zbl 1262.90107 · doi:10.1007/s13366-012-0092-8 |
| [18] | Gennadiy Averkov, Bernardo Gonzalez Merino, Matthias Henze, Ingo Paschke, Stefan Weltge. Tight bounds on discrete quantitative Helly numbers. arXiv:1602.07839 · Zbl 1369.52011 |
| [19] | Averkov, G.; Weismantel, R., Transversal numbers over subsets of linear spaces, Adv. Geom., 12, 1, 19-28 (2012) · Zbl 1250.52006 · doi:10.1515/advgeom.2011.028 |
| [20] | B{\'a}r{\'a}ny, Imre, A generalization of Carath\'eodory’s theorem, Discrete Math., 40, 2-3, 141-152 (1982) · Zbl 0492.52005 · doi:10.1016/0012-365X(82)90115-7 |
| [21] | Borozan, Valentin; Cornu{\'e}jols, G{\'e}rard, Minimal valid inequalities for integer constraints, Math. Oper. Res., 34, 3, 538-546 (2009) · Zbl 1218.90131 · doi:10.1287/moor.1080.0370 |
| [22] | Basu, Amitabh; Conforti, Michele; Cornu{\'e}jols, G{\'e}rard; Zambelli, Giacomo, Maximal lattice-free convex sets in linear subspaces, Math. Oper. Res., 35, 3, 704-720 (2010) · Zbl 1218.90130 · doi:10.1287/moor.1100.0461 |
| [23] | Basu, Amitabh; Conforti, Michele; Di Summa, Marco, A geometric approach to cut-generating functions, Math. Program., 151, 1, Ser. B, 153-189 (2015) · Zbl 1328.90085 · doi:10.1007/s10107-015-0890-5 |
| [24] | J. L Balcazar, Y. Dai, and O. Watanabe, Provably fast training algorithms for support vector machines, Data Mining, 2001. ICDM 2001, Proceedings IEEE International Conference on, IEEE, 2001, pp. 43-50. |
| [25] | Bern, Marshall; Eppstein, David, Optimal M\`“obius transformations for information visualization and meshing. Algorithms and data structures, Providence, RI, 2001, Lecture Notes in Comput. Sci. 2125, 14-25 (2001), Springer, Berlin · Zbl 0997.68536 · doi:10.1007/3-540-44634-6\_3 |
| [26] | Bell, David E., A theorem concerning the integer lattice, Studies in Appl. Math., 56, 2, 187-188 (1976/77) · Zbl 0388.90051 |
| [27] | B{\'a}r{\'a}ny, I.; Fodor, F.; Montejano, L.; Oliveros, D.; P{\'o}r, A., Colourful and fractional \((p,q)\)-theorems, Discrete Comput. Geom., 51, 3, 628-642 (2014) · Zbl 1298.52010 · doi:10.1007/s00454-013-9559-0 |
| [28] | B{\'a}r{\'a}ny, I.; Fodor, F.; Mart{\'{\i }}nez-P{\'e}rez, A.; Montejano, L.; Oliveros, D.; P{\'o}r, A., A fractional Helly theorem for boxes, Comput. Geom., 48, 3, 221-224 (2015) · Zbl 1305.52014 · doi:10.1016/j.comgeo.2014.09.007 |
| [29] | Basu, Saugata; Gabrielov, Andrei; Vorobjov, Nicolai, A Helly-type theorem for semi-monotone sets and monotone maps, Discrete Comput. Geom., 50, 4, 857-864 (2013) · Zbl 1284.14082 · doi:10.1007/s00454-013-9540-y |
| [30] | Briec, Walter; Horvath, Charles, \( \mathbb{B} \)-convexity, Optimization, 53, 2, 103-127 (2004) · Zbl 1144.90506 · doi:10.1080/02331930410001695283 |
| [31] | R. Basri and D. W. Jacobs, Recognition using region correspondences, Int. J. Comput. Vis. 25 (1997), no. 2, 145-166. |
| [32] | B{\'a}r{\'a}ny, Imre; Jer{\'o}nimo-Castro, Jes{\'u}s, Helly type theorems for the sum of vectors in a normed plane, Linear Algebra Appl., 469, 39-50 (2015) · Zbl 1312.52006 · doi:10.1016/j.laa.2014.11.019 |
| [33] | Bj{\'”o}rner, A., Topological methods. Handbook of combinatorics, Vol.1,2, 1819-1872 (1995), Elsevier, Amsterdam · Zbl 0851.52016 |
| [34] | B{\'a}r{\'a}ny, Imre; Katchalski, Meir; Pach, J{\'a}nos, Quantitative Helly-type theorems, Proc. Amer. Math. Soc., 86, 1, 109-114 (1982) · Zbl 0511.52005 · doi:10.2307/2044407 |
| [35] | B{\'a}r{\'a}ny, I.; Katchalski, M.; Pach, J{\'a}nos, Helly’s theorem with volumes, Amer. Math. Monthly, 91, 6, 362-365 (1984) · Zbl 0546.52005 · doi:10.2307/2322144 |
| [36] | Bracho, J.; Montejano, L., Helly-type theorems on the homology of the space of transversals, Discrete Comput. Geom., 27, 3, 387-393 (2002) · Zbl 1021.52005 · doi:10.1007/s00454-001-0076-1 |
| [37] | B{\'a}r{\'a}ny, Imre; Matou{\v{s}}ek, Ji{\v{r}}{\'{\i }}, A fractional Helly theorem for convex lattice sets, Adv. Math., 174, 2, 227-235 (2003) · Zbl 1028.52003 · doi:10.1016/S0001-8708(02)00037-3 |
| [38] | B{\'a}r{\'a}ny, Imre; Matou{\v{s}}ek, Ji{\v{r}}{\'{\i }}, Berge’s theorem, fractional Helly, and art galleries, Discrete Math., 306, 19-20, 2303-2313 (2006) · Zbl 1103.52003 · doi:10.1016/j.disc.2005.12.028 |
| [39] | Boltyanski, Vladimir; Martini, Horst, Jung’s theorem for a pair of Minkowski spaces, Adv. Geom., 6, 4, 645-650 (2006) · Zbl 1151.52006 · doi:10.1515/ADVGEOM.2006.037 |
| [40] | Berg, Deborah E.; Norine, Serguei; Su, Francis Edward; Thomas, Robin; Wollan, Paul, Voting in agreeable societies, Amer. Math. Monthly, 117, 1, 27-39 (2010) · Zbl 1200.91085 · doi:10.4169/000298910X474961 |
| [41] | B\'ar\'any, I.; Onn, S., Carath\'eodory’s theorem, colourful and applicable. Intuitive geometry, Budapest, 1995, Bolyai Soc. Math. Stud. 6, 11-21 (1997), J\'anos Bolyai Math. Soc., Budapest · Zbl 0883.52004 |
| [42] | B{\'a}r{\'a}ny, Imre; Onn, Shmuel, Colourful linear programming and its relatives, Math. Oper. Res., 22, 3, 550-567 (1997) · Zbl 0887.90111 · doi:10.1287/moor.22.3.550 |
| [43] | S. Brazitikos, Brascamp-Lieb inequality and quantitative versions of Helly’s theorem, Mathematika, 63(2017), no. 1, 272-291. DOI: 10/1112/S00255793136000255. · Zbl 1364.26025 |
| [44] | \bysame, Fractional Helly theorem for the diameter of convex sets, to appear in Discrete and Computational Geometry. [math.MG] (2015). |
| [45] | Breen, Marilyn, Starshaped unions and nonempty intersections of convex sets in \({\bf R}^d\), Proc. Amer. Math. Soc., 108, 3, 817-820 (1990) · Zbl 0691.52006 · doi:10.2307/2047806 |
| [46] | Breen, Marilyn, Helly-type theorems for intersections of sets starshaped via orthogonally convex paths, Aequationes Math., 84, 3, 207-217 (2012) · Zbl 1276.52009 · doi:10.1007/s00010-012-0151-0 |
| [47] | Breen, Marilyn, Dual Helly-type theorems for unions of sets starshaped via staircase paths, Ars Combin., 110, 129-141 (2013) · Zbl 1313.52005 |
| [48] | Breen, Marilyn, A Helly-type theorem for intersections of orthogonally starshaped sets in \(\mathbb{R}^d\), Period. Math. Hungar., 68, 1, 45-53 (2014) · Zbl 1299.52010 · doi:10.1007/s10998-014-0014-7 |
| [49] | Bronshte{\u \i }n, E. M., Approximation of convex sets by polyhedra, Sovrem. Mat. Fundam. Napravl.. J. Math. Sci. (N. Y.), 22 153, 6, 727-762 (2008) · Zbl 1161.52001 · doi:10.1007/s10958-008-9144-x |
| [50] | Bj{\`“o}rklund, Henrik; Sandberg, Sven; Vorobyov, Sergei, A discrete subexponential algorithm for parity games. STACS 2003, Lecture Notes in Comput. Sci. 2607, 663-674 (2003), Springer, Berlin · Zbl 1035.68134 · doi:10.1007/3-540-36494-3\_58 |
| [51] | Bacs{\'o}, G{\'a}bor; Tuza, Zsolt, Optimal guard sets and the Helly property, European J. Combin., 32, 1, 28-32 (2011) · Zbl 1213.05185 · doi:10.1016/j.ejc.2010.08.001 |
| [52] | Cuesta-Albertos, J. A.; Nieto-Reyes, A., The random Tukey depth, Comput. Statist. Data Anal., 52, 11, 4979-4988 (2008) · Zbl 1452.62344 · doi:10.1016/j.csda.2008.04.021 |
| [53] | Calafiore, Giuseppe; Campi, M. C., Uncertain convex programs: randomized solutions and confidence levels, Math. Program., 102, 1, Ser. A, 25-46 (2005) · Zbl 1177.90317 · doi:10.1007/s10107-003-0499-y |
| [54] | Calafiore, Giuseppe C.; Campi, Marco C., The scenario approach to robust control design, IEEE Trans. Automat. Control, 51, 5, 742-753 (2006) · Zbl 1366.93457 · doi:10.1109/TAC.2006.875041 |
| [55] | Conforti, Michele; Cornu{\'e}jols, G{\'e}rard; Zambelli, Giacomo, Integer programming, Graduate Texts in Mathematics 271, xii+456 pp. (2014), Springer, Cham · Zbl 1307.90001 · doi:10.1007/978-3-319-11008-0 |
| [56] | Chelnokov, G. R.; Dol’nikov, V. L., On transversals of quasialgebraic families of sets, J. Combin. Theory Ser. A, 125, 194-213 (2014) · Zbl 1295.05257 · doi:10.1016/j.jcta.2014.03.002 |
| [57] | M. Conforti and M. Di Summa, On maximal \(S\)-free convex sets and the parameters \(f(S), h(S)\), to appear in SIAM Journal on Discrete Mathematics. · Zbl 1359.52021 |
| [58] | Colin de Verdi{\`“e}re, {\'”E}ric; Ginot, Gr{\'e}gory; Goaoc, Xavier, Multinerves and Helly numbers of acyclic families. Computational geometry (SCG’12), 209-217 (2012), ACM, New York · Zbl 1293.68286 · doi:10.1145/2261250.2261282 |
| [59] | Colin de Verdi{\`“e}re, {\'”E}ric; Ginot, Gr{\'e}gory; Goaoc, Xavier, Helly numbers of acyclic families, Adv. Math., 253, 163-193 (2014) · Zbl 1301.52019 · doi:10.1016/j.aim.2013.11.004 |
| [60] | Clarkson, Kenneth L.; Eppstein, David; Miller, Gary L.; Sturtivant, Carl; Teng, Shang-Hua, Approximating center points with iterative Radon points, Internat. J. Comput. Geom. Appl., 6, 3, 357-377 (1996) · Zbl 0859.68114 · doi:10.1142/S021819599600023X |
| [61] | Conlon, David; Fox, Jacob; Pach, J{\'a}nos; Sudakov, Benny; Suk, Andrew, Ramsey-type results for semi-algebraic relations, Trans. Amer. Math. Soc., 366, 9, 5043-5065 (2014) · Zbl 1306.14027 · doi:10.1090/S0002-9947-2014-06179-5 |
| [62] | Cheong, Otfried; Goaoc, Xavier; Holmsen, Andreas, Lower bounds to Helly numbers of line transversals to disjoint congruent balls, Israel J. Math., 190, 213-228 (2012) · Zbl 1255.52009 · doi:10.1007/s11856-011-0179-1 |
| [63] | Cheong, Otfried; Goaoc, Xavier; Holmsen, Andreas; Petitjean, Sylvain, Helly-type theorems for line transversals to disjoint unit balls, Discrete Comput. Geom., 39, 1-3, 194-212 (2008) · Zbl 1143.52006 · doi:10.1007/s00454-007-9022-1 |
| [64] | Chan, Timothy M., An optimal randomized algorithm for maximum Tukey depth. Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 430-436 (2004), ACM, New York · Zbl 1317.68246 |
| [65] | Cardinal, Jean; Ito, Hiro; Korman, Matias; Langerman, Stefan, Helly numbers of polyominoes, Graphs Combin., 29, 5, 1221-1234 (2013) · Zbl 1272.05024 · doi:10.1007/s00373-012-1203-x |
| [66] | Clarkson, Kenneth L., Las Vegas algorithms for linear and integer programming when the dimension is small, J. Assoc. Comput. Mach., 42, 2, 488-499 (1995) · Zbl 0885.65063 · doi:10.1145/201019.201036 |
| [67] | Demouth, Julien; Devillers, Olivier; Glisse, Marc; Goaoc, Xavier, Helly-type theorems for approximate covering, Discrete Comput. Geom., 42, 3, 379-398 (2009) · Zbl 1178.52004 · doi:10.1007/s00454-009-9167-1 |
| [68] | Debrunner, H. E., Helly type theorems derived from basic singular homology, Amer. Math. Monthly, 77, 375-380 (1970) · Zbl 0191.54903 |
| [69] | Deza, M.; Frankl, P., A Helly type theorem for hypersurfaces, J. Combin. Theory Ser. A, 45, 1, 27-30 (1987) · Zbl 0614.52008 · doi:10.1016/0097-3165(87)90043-4 |
| [70] | Danzer, Ludwig; Gr{\`“u}nbaum, Branko; Klee, Victor, Helly”s theorem and its relatives. Proc. Sympos. Pure Math., Vol. VII, 101-180 (1963), Amer. Math. Soc., Providence, R.I. · Zbl 0132.17401 |
| [71] | J. A. DeLorea, R. N. La Haye, D. Oliveros, and E. Roldan-Pensado. Beyond Chance-Constrained Convex Mixed-Integer Optimization: A Generalized Calafiore-Campi Algorithm and the notion of \(S\)-optimization. Preprint available at arXiv: 1504.00076. (2015). |
| [72] | J. A. De Loera, R. N. La Haye, D. Oliveros, and E. Roldan-Pensado, Helly numbers of algebraic subsets \(R^d\) and an extension of Doignon’s theorem, arXiv:1508.02380 [math.MG] (2015). To appear in Advances in Geometry. · Zbl 1431.52011 |
| [73] | J. A. De Loera, R. N. La Haye, D. Rolnick, and P Soberon, Quantitative Tverberg, Helly, & Caratheodory theorems, arXiv:1503.06116 [math.MG] (2015). · Zbl 1386.52004 |
| [74] | J. A. De Lorea, R. N. La Haye, D. Rolnick, and P. Soberon. Quantitative Tverberg theorems over lattices and other discrete sets. To appear in Discrete and Compt. Geometry. · Zbl 1386.52004 |
| [75] | J. A. De Lorea, R. N. La Haye, D. Rolnick, and P. Soberon. Quantitative combinatorial geometry for continuous parameters. To appear in Discrete and Compt. Geometry. · Zbl 1369.52012 |
| [76] | J. A. De Loera, S. Petrovic, and D. Stasi, Random sampling in computational algebra: Helly numbers and violator spaces, Journal of Symbolic Computation, 77, pp. 1-15 (2016). · Zbl 1357.68302 |
| [77] | Doignon, Jean-Paul, Convexity in cristallographical lattices, J. Geometry, 3, 71-85 (1973) · Zbl 0245.52004 |
| [78] | Doignon, Jean-Paul; Reay, John R.; Sierksma, Gerard, A Tverberg-type generalization of the Helly number of a convexity space, J. Geom., 16, 2, 117-125 (1981) · Zbl 0468.52002 · doi:10.1007/BF01917580 |
| [79] | Domokos, M{\'a}ty{\'a}s; Szab{\'o}, Endre, Helly dimension of algebraic groups, J. Lond. Math. Soc. (2), 84, 1, 19-34 (2011) · Zbl 1231.13006 · doi:10.1112/jlms/jdq101 |
| [80] | Eckhoff, J{\`“u}rgen, An upper-bound theorem for families of convex sets, Geom. Dedicata, 19, 2, 217-227 (1985) · Zbl 0588.52012 · doi:10.1007/BF00181472 |
| [81] | Eckhoff, J{\`“u}rgen, Helly, Radon, and Carath\'”eodory type theorems. Handbook of convex geometry, Vol.A, B, 389-448 (1993), North-Holland, Amsterdam · Zbl 0791.52009 |
| [82] | Eckhoff, J{\`“u}rgen, A survey of the Hadwiger-Debrunner \((p,q)\)-problem. Discrete and computational geometry, Algorithms Combin. 25, 347-377 (2003), Springer, Berlin · Zbl 1084.52002 · doi:10.1007/978-3-642-55566-4\_16 |
| [83] | Eckhoff, J{\`“u}rgen, Common transversals in the plane: the fractional perspective, European J. Combin., 29, 8, 1872-1880 (2008) · Zbl 1156.52006 · doi:10.1016/j.ejc.2008.01.020 |
| [84] | Erd{\H{o}}s, Paul; Gallai, Tibor, On the minimal number of vertices representing the edges of a graph., Magyar Tud. Akad. Mat. Kutat\'o Int. K\`“ozl., 6, 181-203 (1961) · Zbl 0101.41001 |
| [85] | Eisenbrand, Friedrich, Fast integer programming in fixed dimension. Algorithms-ESA 2003, Lecture Notes in Comput. Sci. 2832, 196-207 (2003), Springer, Berlin · Zbl 1266.90130 · doi:10.1007/978-3-540-39658-1\_20 |
| [86] | Ewald, G.; Larman, D. G.; Rogers, C. A., The directions of the line segments and of the \(r\)-dimensional balls on the boundary of a convex body in Euclidean space, Mathematika, 17, 1-20 (1970) · Zbl 0199.57002 |
| [87] | Eckhoff, J{\`“u}rgen; Nischke, Klaus-Peter, Morris”s pigeonhole principle and the Helly theorem for unions of convex sets, Bull. Lond. Math. Soc., 41, 4, 577-588 (2009) · Zbl 1181.52011 · doi:10.1112/blms/bdp024 |
| [88] | Farb, Benson, Group actions and Helly’s theorem, Adv. Math., 222, 5, 1574-1588 (2009) · Zbl 1177.22007 · doi:10.1016/j.aim.2009.06.004 |
| [89] | Fefferman, Charles L., A sharp form of Whitney’s extension theorem, Ann. of Math. (2), 161, 1, 509-577 (2005) · Zbl 1102.58005 · doi:10.4007/annals.2005.161.509 |
| [90] | O. Friedmann, T. Dueholm Hansen, and U. Zwick, Random-facet and random-bland require subexponential time even for shortest paths, arXiv:1410.7530 [cs.DS] (2014). |
| [91] | Fl{\o }ystad, Gunnar, The colorful Helly theorem and colorful resolutions of ideals, J. Pure Appl. Algebra, 215, 6, 1255-1262 (2011) · Zbl 1219.13007 · doi:10.1016/j.jpaa.2010.08.009 |
| [92] | J. Fox, J. Pach, and A. Suk, Density and regularity theorems for semi-algebraic hypergraphs, SODA ’15: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, January 2015, pp. 1517-1530. · Zbl 1375.05185 |
| [93] | Frankl, P., Helly-type theorems for varieties, European J. Combin., 10, 3, 243-245 (1989) · Zbl 0679.14002 · doi:10.1016/S0195-6698(89)80058-7 |
| [94] | G{\'”a}rtner, Bernd, A subexponential algorithm for abstract optimization problems, SIAM J. Comput., 24, 5, 1018-1035 (1995) · Zbl 0836.68044 · doi:10.1137/S0097539793250287 |
| [95] | G{\'”a}rtner, Bernd, Sampling with removal in LP-type problems, J. Comput. Geom., 6, 2, 93-112 (2015) · Zbl 1405.90146 |
| [96] | Goodman, J. E.; Holmsen, A.; Pollack, R.; Ranestad, K.; Sottile, F., Cremona convexity, frame convexity and a theorem of Santal\'o, Adv. Geom., 6, 2, 301-321 (2006) · Zbl 1105.52004 · doi:10.1515/ADVGEOM.2006.018 |
| [97] | Gao, Jie; Langberg, Michael; Schulman, Leonard J., Clustering lines in high-dimensional space: classification of incomplete data, ACM Trans. Algorithms, 7, 1, Art. 8, 26 pp. (2010) · Zbl 1295.68199 · doi:10.1145/1868237.1868246 |
| [98] | Gr{\`“u}nbaum, Branko; Motzkin, Theodore S., On components in some families of sets, Proc. Amer. Math. Soc., 12, 607-613 (1961) · Zbl 0106.01001 |
| [99] | Gaubert, St{\'e}phane; Meunier, Fr{\'e}d{\'e}ric, Carath\'eodory, Helly and the others in the max-plus world, Discrete Comput. Geom., 43, 3, 648-662 (2010) · Zbl 1219.14071 · doi:10.1007/s00454-009-9207-x |
| [100] | G{\`“a}rtner, B.; Matou{\v{s}}ek, J.; R{\'”u}st, L.; Skovro{\v{n}}, P., Violator spaces: structure and algorithms, Discrete Appl. Math., 156, 11, 2124-2141 (2008) · Zbl 1163.90651 · doi:10.1016/j.dam.2007.08.048 |
| [101] | Goaoc, Xavier, Some discrete properties of the space of line transversals to disjoint balls. Nonlinear computational geometry, IMA Vol. Math. Appl. 151, 51-83 (2010), Springer, New York · Zbl 1208.52006 · doi:10.1007/978-1-4419-0999-2\_3 |
| [102] | Gomory, Ralph E., Outline of an algorithm for integer solutions to linear programs, Bull. Amer. Math. Soc., 64, 275-278 (1958) · Zbl 0085.35807 |
| [103] | Goaoc, Xavier; Pat{\'a}k, Pavel; Pat{\'a}kov{\'a}, Zuzana; Tancer, Martin; Wagner, Uli, Bounding Helly numbers via Betti numbers. 31st International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform. 34, 507-521 (2015), Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern · Zbl 1387.52011 |
| [104] | Gr{\'”u}nbaum, B., On common transversals, Arch. Math., 9, 465-469 (1958) · Zbl 0083.17204 |
| [105] | Gruber, Peter M., Aspects of approximation of convex bodies. Handbook of convex geometry, Vol.A, B, 319-345 (1993), North-Holland, Amsterdam · Zbl 0791.52007 |
| [106] | Hadwiger, H., Ueber Eibereiche mit gemeinsamer Treffgeraden, Portugal. Math., 16, 23-29 (1957) · Zbl 0081.16404 |
| [107] | Halman, Nir, Discrete and lexicographic Helly-type theorems, Discrete Comput. Geom., 39, 4, 690-719 (2008) · Zbl 1157.52006 · doi:10.1007/s00454-007-9028-8 |
| [108] | Halman, Nir, Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems, Algorithmica, 49, 1, 37-50 (2007) · Zbl 1131.91012 · doi:10.1007/s00453-007-0175-3 |
| [109] | Hadwiger, H.; Debrunner, H., \`“Uber eine Variante zum Hellyschen Satz, Arch. Math. (Basel), 8, 309-313 (1957) · Zbl 0080.15404 |
| [110] | E. Helly, Uber mengen konvexer korper mit gemeinschaftlichen punkte., Jahresbericht der Deutschen Mathematiker-Vereinigung 32 (1923), 175-176. · JFM 49.0534.02 |
| [111] | Helly, Eduard, \`“Uber Systeme von abgeschlossenen Mengen mit gemeinschaftlichen Punkten, Monatsh. Math. Phys., 37, 1, 281-302 (1930) · JFM 56.0499.03 · doi:10.1007/BF01696777 |
| [112] | S. Hell, Tverberg-type theorems and the fractional helly property, Ph.D. thesis, Technische Universitat Berlin, 2006, https://opus4.kobv.de/opus4-tuberlin/frontdoor/index/index/docId/1371. · Zbl 1235.52002 |
| [113] | A. Holmsen and R. Karasev, Colorful theorems for strong convextity, arXiv:1509.08783 [math.CO] (2015). To appear in the Proc. Amer. Math. Soc. · Zbl 1364.52006 |
| [114] | Holmsen, Andreas; Katchalski, Meir; Lewis, Ted, A Helly-type theorem for line transversals to disjoint unit balls, Discrete Comput. Geom., 29, 4, 595-602 (2003) · Zbl 1030.52008 · doi:10.1007/s00454-002-0793-0 |
| [115] | Holmsen, Andreas F.; Martinez-Sandoval, Leonardo; Montejano, Luis, A geometric Hall-type theorem, Proc. Amer. Math. Soc., 144, 2, 503-511 (2016) · Zbl 1331.05219 · doi:10.1090/proc12733 |
| [116] | Hoffman, A. J., Binding constraints and Helly numbers. Second International Conference on Combinatorial Mathematics (New York, 1978), Ann. New York Acad. Sci. 319, 284-288 (1979), New York Acad. Sci., New York · Zbl 0489.52011 |
| [117] | Holmsen, Andreas F., Geometric transversal theory: \(T(3)\)-families in the plane. Geometry-intuitive, discrete, and convex, Bolyai Soc. Math. Stud. 24, 187-203 (2013), J\'anos Bolyai Math. Soc., Budapest · Zbl 1359.52003 · doi:10.1007/978-3-642-41498-5\_7 |
| [118] | Holmsen, Andreas F.; Pach, J{\'a}nos; Tverberg, Helge, Points surrounding the origin, Combinatorica, 28, 6, 633-644 (2008) · Zbl 1199.52013 · doi:10.1007/s00493-008-2427-5 |
| [119] | A. F. Holmsen and E. Roldan-Pensado, The colored Hadwiger transversal theorem in \(R^d\), Combinatorica, 36:417(2016). DOI:10.1007/s00493-014-3192-2. · Zbl 1399.52012 |
| [120] | Jamison-Waldner, Robert E., Partition numbers for trees and ordered sets, Pacific J. Math., 96, 1, 115-140 (1981) · Zbl 0482.52010 |
| [121] | Jer{\'o}nimo Castro, Jes{\'u}s, Line transversals to translates of unit discs, Discrete Comput. Geom., 37, 3, 409-417 (2007) · Zbl 1117.52005 · doi:10.1007/s00454-006-1281-8 |
| [122] | J. Jeronimo-Castro, A. Magazinov, and P Soberon, On a problem by Dol’nikov, Discrete Math. 338 (2015), no. 9. · Zbl 1317.52013 |
| [123] | Jer{\'o}nimo-Castro, J.; Rold{\'a}n-Pensado, E., Line transversals to translates of a convex body, Discrete Comput. Geom., 45, 2, 329-339 (2011) · Zbl 1211.52002 · doi:10.1007/s00454-010-9293-9 |
| [124] | Kalai, Gil, Intersection patterns of convex sets, Israel J. Math., 48, 2-3, 161-174 (1984) · Zbl 0557.52005 · doi:10.1007/BF02761162 |
| [125] | G. Kalai, A subexponential randomized simplex algorithm, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, ACM, 1992, pp. 475-482. |
| [126] | Karasev, R. N., Transversals for families of translates of a two-dimensional convex compact set, Discrete Comput. Geom., 24, 2-3, 345-353 (2000) · Zbl 0959.52005 · doi:10.1007/s004540010040 |
| [127] | Karasev, Roman N., Analogues of the central point theorem for families with \(d\)-intersection property in \(\mathbb{R}^d\), Combinatorica, 32, 6, 689-702 (2012) · Zbl 1324.52004 · doi:10.1007/s00493-012-2603-5 |
| [128] | Kleitman, Daniel J.; Gy{\'a}rf{\'a}s, Andr{\'a}s; T{\'o}th, G{\'e}za, Convex sets in the plane with three of every four meeting, Combinatorica, 21, 2, 221-232 (2001) · Zbl 0981.52001 · doi:10.1007/s004930100020 |
| [129] | Katchalski, M.; Liu, A., A problem of geometry in \({\bf R}^n\), Proc. Amer. Math. Soc., 75, 2, 284-288 (1979) · Zbl 0418.52013 · doi:10.2307/2042758 |
| [130] | Kalai, Gil; Meshulam, Roy, A topological colorful Helly theorem, Adv. Math., 191, 2, 305-311 (2005) · Zbl 1064.52008 · doi:10.1016/j.aim.2004.03.009 |
| [131] | Kalai, Gil; Meshulam, Roy, Leray numbers of projections and a topological Helly-type theorem, J. Topol., 1, 3, 551-556 (2008) · Zbl 1148.55014 · doi:10.1112/jtopol/jtn010 |
| [132] | Knauer, Christian; Tiwary, Hans Raj; Werner, Daniel, On the computational complexity of ham-sandwich cuts, Helly sets, and related problems. 28th International Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform. 9, 649-660 (2011), Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern · Zbl 1230.68111 |
| [133] | Kay, David C.; Womble, Eugene W., Axiomatic convexity theory and relationships between the Carath\'eodory, Helly, and Radon numbers, Pacific J. Math., 38, 471-485 (1971) · Zbl 0235.52001 |
| [134] | Lenstra, H. W., Jr., Integer programming with a fixed number of variables, Math. Oper. Res., 8, 4, 538-548 (1983) · Zbl 0524.90067 · doi:10.1287/moor.8.4.538 |
| [135] | Lov{\'a}sz, L{\'a}szl{\'o}, Geometry of numbers and integer programming. Mathematical programming, Tokyo, 1988, Math. Appl. (Japanese Ser.) 6, 177-201 (1989), SCIPRESS, Tokyo · Zbl 0683.90054 |
| [136] | Matou{\v{s}}ek, Ji{\v{r}}{\'{\i }}, Lower bounds for a subexponential optimization algorithm, Random Structures Algorithms, 5, 4, 591-607 (1994) · Zbl 0824.90094 · doi:10.1002/rsa.3240050408 |
| [137] | Matou{\v{s}}ek, J., A Helly-type theorem for unions of convex sets, Discrete Comput. Geom., 18, 1, 1-12 (1997) · Zbl 0889.52009 · doi:10.1007/PL00009305 |
| [138] | Matou{\v{s}}ek, Ji{\v{r}}{\'{\i }}, Lectures on discrete geometry, Graduate Texts in Mathematics 212, xvi+481 pp. (2002), Springer-Verlag, New York · Zbl 0999.52006 · doi:10.1007/978-1-4613-0039-7 |
| [139] | Matou{\v{s}}ek, Ji{\v{r}}{\'{\i }}, Bounded VC-dimension implies a fractional Helly theorem, Discrete Comput. Geom., 31, 2, 251-255 (2004) · Zbl 1059.52012 · doi:10.1007/s00454-003-2859-z |
| [140] | Matou{\v{s}}ek, Ji{\v{r}}{\'{\i }}, Geometric discrepancy, Algorithms and Combinatorics 18, xii+288 pp. (1999), Springer-Verlag, Berlin · Zbl 1197.11092 · doi:10.1007/978-3-642-03942-3 |
| [141] | N. Megiddo, Program product for displaying a line passing through a plurality of boxes, July 2 1996, US Patent 5,533,178. |
| [142] | Montejano, Luis; Oliveros, Deborah, Colourful transversal theorems, Contrib. Discrete Math., 3, 2, 60-75 (2008) · Zbl 1204.52010 |
| [143] | Montejano, L.; Oliveros, D., Tolerance in Helly-type theorems, Discrete Comput. Geom., 45, 2, 348-357 (2011) · Zbl 1216.52006 · doi:10.1007/s00454-010-9296-6 |
| [144] | Montejano, L., Transversals, topology and colorful geometric results. Geometry-intuitive, discrete, and convex, Bolyai Soc. Math. Stud. 24, 205-218 (2013), J\'anos Bolyai Math. Soc., Budapest · Zbl 1359.52007 · doi:10.1007/978-3-642-41498-5\_8 |
| [145] | Montejano, Luis, A new topological Helly theorem and some transversal results, Discrete Comput. Geom., 52, 2, 390-398 (2014) · Zbl 1322.52006 · doi:10.1007/s00454-014-9613-6 |
| [146] | Morris, Howard Cary, TWO PIGEON-HOLE PRINCIPLES AND UNIONS OF CONVEXLY-DISJOINT SETS, 77 pp. (1974), ProQuest LLC, Ann Arbor, MI |
| [147] | Motzkin, Theodore S., A proof of Hilbert’s Nullstellensatz, Math. Z., 63, 341-344 (1955) · Zbl 0068.25201 |
| [148] | G. L. Miller and D. R Sheehy, Approximate center points with proofs, Proceedings of the twenty-fifth annual symposium on Computational geometry, ACM, 2009, pp. 153-158. · Zbl 1388.68288 |
| [149] | Montejano, Luis; Sober{\'o}n, Pablo, Piercing numbers for balanced and unbalanced families, Discrete Comput. Geom., 45, 2, 358-364 (2011) · Zbl 1217.52004 · doi:10.1007/s00454-010-9295-7 |
| [150] | J. Matousek, M. Sharir, and E. Welzl, A subexponential bound for linear programming, Algorithmica 16 (1996), no. 4-5, 498-516. · Zbl 0857.68119 |
| [151] | Matou{\v{s}}ek, Ji{\v{r}}{\'{\i }}; Tancer, Martin, Dimension gaps between representability and collapsibility, Discrete Comput. Geom., 42, 4, 631-639 (2009) · Zbl 1201.52003 · doi:10.1007/s00454-008-9091-9 |
| [152] | Mulzer, Wolfgang; Werner, Daniel, Approximating Tverberg points in linear time for any fixed dimension, Discrete Comput. Geom., 50, 2, 520-535 (2013) · Zbl 1298.68281 · doi:10.1007/s00454-013-9528-7 |
| [153] | Nasz{\'o}di, M{\'a}rton, Proof of a conjecture of B\'ar\'any, Katchalski and Pach, Discrete Comput. Geom., 55, 1, 243-248 (2016) · Zbl 1339.52009 · doi:10.1007/s00454-015-9753-3 |
| [154] | Neumann, B. H., On an invariant of plane regions and mass distributions, J. London Math. Soc., 20, 226-237 (1945) · Zbl 0063.05928 |
| [155] | Nitica, Viorel; Sergeev, Serge{\u \i }, Tropical convexity over max-min semiring. Tropical and idempotent mathematics and applications, Contemp. Math. 616, 241-260 (2014), Amer. Math. Soc., Providence, RI · Zbl 1320.52002 · doi:10.1090/conm/616/12301 |
| [156] | Pollack, R.; Wenger, R., Necessary and sufficient conditions for hyperplane transversals, Combinatorica, 10, 3, 307-311 (1990) · Zbl 0722.52005 · doi:10.1007/BF02122783 |
| [157] | Radon, Johann, Mengen konvexer K\`“orper, die einen gemeinsamen Punkt enthalten, Math. Ann., 83, 1-2, 113-115 (1921) · JFM 48.0834.04 · doi:10.1007/BF01464231 |
| [158] | Rado, R., A theorem on general measure, J. London Math. Soc., 21, 291-300 (1947) (1946) · Zbl 0061.09606 |
| [159] | D. Rolnick and P. Soberon, Quantitative \((p,q)\) theorems in combinatorial geometry, arXiv:1504.01642 [math.MG] (2015). · Zbl 1379.52007 |
| [160] | Reisner, Shlomo; Sch{\`“u}tt, Carsten; Werner, Elisabeth, Dropping a vertex or a facet from a convex polytope, Forum Math., 13, 3, 359-378 (2001) · Zbl 0980.52002 · doi:10.1515/form.2001.012 |
| [161] | Scarf, Herbert E., An observation on the structure of production sets with indivisibilities, Proc. Nat. Acad. Sci. U.S.A., 74, 9, 3637-3641 (1977) · Zbl 0381.90081 |
| [162] | Schrijver, Alexander, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, xii+471 pp. (1986), John Wiley & Sons, Ltd., Chichester · Zbl 0970.90052 |
| [163] | Seidel, Raimund, Small-dimensional linear programming and convex hulls made easy, Discrete Comput. Geom., 6, 5, 423-434 (1991) · Zbl 0747.90066 · doi:10.1007/BF02574699 |
| [164] | P. Skovron, Abstract models of optimization problems, Ph.D. thesis, Charles University, Prague, 2007. |
| [165] | P. Soberon, Helly-type theorems for the diameter, to appear Bulletin of the London Mathematical Society (2016). · Zbl 1353.52005 |
| [166] | Sharir, Micha; Welzl, Emo, A combinatorial bound for linear programming and related problems. STACS 92, Cachan, 1992, Lecture Notes in Comput. Sci. 577, 569-579 (1992), Springer, Berlin · Zbl 1494.68276 |
| [167] | Micha Sharir and Emo Welzl, Rectilinear and polygonal p-piercing and p-center problems, Proceedings of the twelfth annual symposium on Computational geometry, ACM, 1996, pp. 122-132. |
| [168] | Swanepoel, Konrad J., Helly-type theorems for homothets of planar convex curves, Proc. Amer. Math. Soc., 131, 3, 921-932 (electronic) (2003) · Zbl 1021.52006 · doi:10.1090/S0002-9939-02-06722-9 |
| [169] | Tancer, Martin, Intersection patterns of convex sets via simplicial complexes: a survey. Thirty essays on geometric graph theory, 521-540 (2013), Springer, New York · Zbl 1276.52010 · doi:10.1007/978-1-4614-0110-0\_28 |
| [170] | Tuza, Zsolt, Minimum number of elements representing a set system of given rank, J. Combin. Theory Ser. A, 52, 1, 84-89 (1989) · Zbl 0682.05005 · doi:10.1016/0097-3165(89)90064-2 |
| [171] | Tverberg, H., A generalization of Radon’s theorem, J. London Math. Soc., 41, 123-128 (1966) · Zbl 0131.20002 |
| [172] | Tverberg, Helge, Proof of Gr\`“unbaum”s conjecture on common transversals for translates, Discrete Comput. Geom., 4, 3, 191-203 (1989) · Zbl 0686.52008 · doi:10.1007/BF02187722 |
| [173] | van de Vel, M. L. J., Theory of convex structures, North-Holland Mathematical Library 50, xvi+540 pp. (1993), North-Holland Publishing Co., Amsterdam · Zbl 0785.52001 |
| [174] | Wegner, Gerd, \(d\)-collapsing and nerves of families of convex sets, Arch. Math. (Basel), 26, 317-321 (1975) · Zbl 0308.52005 |
| [175] | Wenger, Rephael, Helly-type theorems and geometric transversals. Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., 63-82 (1997), CRC, Boca Raton, FL · Zbl 0912.52006 |
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.
