Given a set $S \subseteq \mathbb{R}^2$, define the \emph{Helly number of $S$}, denoted by $H(S)$, as the smallest positive integer $N$, if it exists, for which the following statement is true: for any finite family $\mathcal{F}$ of convex sets in~$\mathbb{R}^2$ such that the intersection of any $N$ or fewer members of~$\mathcal{F}$ contains at least one point of $S$, there is a point of $S$ common to all members of $\mathcal{F}$. We prove that the Helly numbers of \emph{exponential lattices} $\{α^n \colon n \in \mathbb{N}_0\}^2$ are finite for every $α>1$ and we determine their exact values in some instances. In particular, we obtain $H(\{2^n \colon n \in \mathbb{N}_0\}^2)=5$, solving a problem posed by Dillon (2021). For real numbers $α, β> 1$, we also fully characterize exponential lattices $L(α,β) = \{α^n \colon n \in \mathbb{N}_0\} \times \{β^n \colon n \in \mathbb{N}_0\}$ with finite Helly numbers by showing that $H(L(α,β))$ is finite if and only if $\log_α(β)$ is rational.

Abstract We present algorithms for the $$(1+\epsilon )$$ ( 1 + ϵ ) -approximate version of the closest vector problem for certain norms. The currently fastest algorithm (Dadush and Kun 2016) for general norms in dimension n has running time of $$2^{O(n)}(1/\epsilon )^n$$ 2 O ( n ) ( 1 / ϵ ) n . We improve this substantially in the following two cases. First, for $$\ell _p$$ ℓ p -norms with $$p>2$$ p > 2 (resp. $$p \in [1,2]$$ p ∈ [ 1 , 2 ] ) fixed, we present an algorithm with a running time of $$2^{O(n)}(1+1/\epsilon )^{n/2}$$ 2 O ( n ) ( 1 + 1 / ϵ ) n / 2 (resp. $$2^{O(n)} (1+1/\epsilon )^{n/p}$$ 2 O ( n ) ( 1 + 1 / ϵ ) n / p ). This result is based on a geometric covering problem, that was introduced in the context of CVP by Eisenbrand et al.: How many convex bodies are needed to cover the ball of the norm such that, if scaled by factor 2 around their centroids, each one is contained in the $$(1+\epsilon )$$ ( 1 + ϵ ) -scaled homothet of the norm ball? We provide upper bounds for this $$(2,\epsilon )$$ ( 2 , ϵ ) -covering number by exploiting the modulus of smoothness of the $$\ell _p$$ ℓ

We introduce a new variant of quantitative Helly-type theorems: the minimal homothetic distance of the intersection of a family of convex sets to the intersection of a subfamily of a fixed size. As an application, we establish the following quantitative Helly-type result for the diameter. If $K$ is the intersection of finitely many convex bodies in $\mathbb{R}^d$, then one can select $2d$ of these bodies whose intersection is of diameter at most $(2d)^3{diam}(K)$. The best previously known estimate, due to Brazitikos [ Bull. Hellenic Math. Soc., 62 (2018), pp. 19--25], is $c d^{11/2}$. Moreover, we confirm that the multiplicative factor $c d^{1/2}$ conjectured by Bárány, Katchalski, and Pach [ Proc. Amer. Math. Soc., 86 (1982), pp. 109--114] cannot be improved. The bounds above follow from our key result that concerns sparse approximation of a convex polytope by the convex hull of a well-chosen subset of its vertices: Assume that $Q \subset {\mathbb R}^d$ is a polytope whose centroid is the origin. Then there exist at most 2d vertices of $Q$ whose convex hull $Q^{\prime \prime}$ satisfies $Q \subset - 8d^3 Q^{\prime \prime}.$