Generalized barycentric coordinates and approximations of convex functions on arbitrary convex polytopes

摘要

In this paper, we study the error in the approximation of a convex function obtained via a one-parameter family of approximation schemes, which we refer to as barycentric approximation schemes. For a given finite set of pairwise distinct points X_n := (X_j)_(i=0)~n in R~d, the barycentric approximation of a convex function/ is of the form: B|f|(x)=nΣi=0 λ_i(x)f(x_i), where (λ_i)_(i=0)~n is a set of barycentric coordinates with respect to the point set X_n. The main content of this paper is two-fold. The first goal is to derive sharp upper and lower bounds on all barycentric coordinates over the convex polytope conv(X_n). The second objective of the paper is to exploit the convexity assumption heavily and establish a number of upper and lower pointwise bounds on the approximation error for approximating arbitrary convex functions. These bounds depend solely on computable quantities related to the data values of the function, the largest and smallest barycentric coordinates. For convex twice continuously differentiable functions, we derive an optimal error estimate. We show that the Delaunay triangulation gives access to efficient algorithms for computing optimal barycentric approximation. Finally, numerical examples are used to show the success of the method.