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 - Kaibel, Volker A1 - Weltge, Stefan T1 - Maximum semidefinite and linear extension complexity of families of polytopes T2 - arXiv.org : (math) Y1 - 2016 UR - https://arxiv.org/abs/1605.08538 SP - 11 ER - TY - GEN A1 - Averkov, Gennadiy A1 - Langfeld, Barbara T1 - Homometry and direct-sum decompositions of lattice-convex sets T2 - Discrete & computational geometry : an international journal of mathematics and computer science N2 - Two sets in Rd are called homometric if they have the same covariogram, where the covariogram of a finite subset K of Rd is the function associating to each u∈Rd the cardinality of K∩(K+u). Understanding the structure of homometric sets is important for a number of areas of mathematics and applications. If two sets are homometric but do not coincide up to translations and point reflections, we call them nontrivially homometric. We study nontrivially homometric pairs of lattice-convex sets, where a set K is called lattice-convex with respect to a lattice M⊆Rd if K is the intersection of M and a convex subset of Rd. This line of research was initiated in 2005 by Daurat, Gérard and Nivat and, independently, by Gardner, Gronchi and Zong. All pairs of nontrivially homometric lattice-convex sets that have been known so far can essentially be written as direct sums S⊕T and S⊕(−T), where T is lattice-convex, the underlying lattice M is the direct sum of T and some sublattice L, and S is a subset of L. We study pairs of nontrivially homometric lattice-convex sets assuming this particular form and establish a necessary and a sufficient condition for the lattice-convexity of S⊕T. This allows us to explicitly describe all nontrivially homometric pairs in dimension two, under the above assumption, and to construct examples of nontrivially homometric pairs of lattice-convex sets for each d≥3. KW - Covariogram problem KW - Diffraction KW - Discrete tomography KW - Direct sum KW - Homometric sets KW - Lattice-convex set Y1 - 2016 UR - https://link.springer.com/article/10.1007%2Fs00454-016-9786-2 U6 - https://doi.org/10.1007/s00454-016-9786-2 SN - 1432-0444 SN - 0179-5376 VL - 56 IS - 1 SP - 216 EP - 249 ER -