TY - GEN A1 - Averkov, Gennadiy A1 - González Merino, Bernardo A1 - Henze, Matthias A1 - Paschke, Ingo A1 - Weltge, Stefan T1 - Tight bounds on discrete quantitative Helly numbers T2 - arXiv.org : (math) N2 - Given a subset S of R^n, let c(S,k) be the smallest number t such that whenever finitely many convex sets have exactly k common points in S, there exist at most t of these sets that already have exactly k common points in S. For S = Z^n, this number was introduced by Aliev et al. [2014] who gave an explicit bound showing that c(Z^n,k) = O(k) holds for every fixed n. Recently, Chestnut et al. [2015] improved this to c(Z^n,k) = O(k (log log k)(log k)^{-1/3} ) and provided the lower bound c(Z^n,k) = Omega(k^{(n-1)/(n+1)}). We provide a combinatorial description of c(S,k) in terms of polytopes with vertices in S and use it to improve the previously known bounds as follows: We strengthen the bound of Aliev et al. [2014] by a constant factor and extend it to general discrete sets S. We close the gap for Z^n by showing that c(Z^n,k) = Theta(k^{(n-1)/(n+1)}) holds for every fixed n. Finally, we determine the exact values of c(Z^n,k) for all k <= 4. KW - Metric Geometry KW - Optimization and Control Y1 - 2016 UR - https://arxiv.org/abs/1602.07839 ER - TY - GEN A1 - Averkov, Gennadiy A1 - González Merino, Bernardo A1 - Paschke, Ingo A1 - Schymura, Matthias A1 - Weltge, Stefan T1 - Tight bounds on discrete quantitative Helly numbers T2 - Advances in Applied Mathematics Y1 - 2017 UR - https://www.sciencedirect.com/science/article/abs/pii/S019688581730043X U6 - https://doi.org/10.1016/j.aam.2017.04.003 SN - 0196-8858 VL - 89 SP - 76 EP - 101 ER -