Extremal Approximately Convex Functions and Estimating the Size of Convex Hulls

Abstract

A real valued function $f$ defined on a convex $K$ is anemconvex function iff it satisfies $$f((x+y)/2)\le (f(x)+f(y))/2+1.$$ A thorough study of approximately convex functions is made. The principal results are a sharp universal upper bound for lower semi-continuous approximately convex functions that vanish on the vertices of a simplex and an explicit description of the unique largest bounded approximately convex function~$E$ vanishing on the vertices of a simplex. A set $A$ in a normed space is an approximately convex set iff for all $a,b\in A$ the distance of the midpoint $(a+b)/2$ to $A$ is $\le 1$. The bounds on approximately convex functions are used to show that in ${\mathbb{R}}^n$ with the Euclidean norm, for any approximately convex set $A$, any point $z$ of the convex hull of $A$ is at a distance of at most $[{\log }_2(n-1)]+1+(n-1)/2^{[{\log }_2(n-1)]}$ from $A$. Examples are given to show this is the sharp bound. Bounds for general norms on $R^n$ are also given.

39 pages. See also http://www.math.sc.edu/~howard/