Extremal approximately convex functions and estimating the size of convex hulls (Q1969013): Difference between revisions

The main result in this paper states that for any norm \(\|\cdot\|\) in \(\mathbb{R}^n\) there is a constant \(C_{\|\cdot\|}\) such that, for every \(A\subset \mathbb{R}^n\) and \(z\) in the convex hull of \(A\), one has \[ \text{dist}(z,A)\leq C_{\|\cdot\|} \sup_{a_0,a_1\in A} \text{dist}(\textstyle{{1\over 2}}(a_0+ a_1), A), \] where \(\text{dist}(x, A):= \inf\{\|x- a\|: a\in A\}\). The sharp constant \(C_{\|\cdot\|}\) satisfies \(\kappa(n-1)\leq C_{\|\cdot\|}\kappa(n)\), with \(\kappa(n)= [\log_2(n)]+ 1+{n\over 2^{[\log_2(n)]}}\) (\([\cdot]\) denoting the greatest integer function), and \(C_{\|\cdot\|}= \kappa(n-1)\) if \(\|\cdot\|\) is the Euclidean norm. The lower bound on \(C_{\|\cdot\|}\) follows from an explicit computation of the largest bounded approximately convex function on the standard \(n\)-dimensional simplex which takes non-positive values on the vertices (a real-valued function \(h\) defined on a convex subset \(E\) of a normed space is said to be approximately convex iff for all \(a,b\in E\) it satisfies \(h({1\over 2}(a+ b))\leq {1\over 2}(h(a)+ h(b)+ 1)\). To apply this computation to the derivation of the main result one considers approximately convex sets, that is, sets \(A\) for which the function \(\text{dist}(.,A)\) is approximately convex.