An algorithm for discrete approximation by quasi-convex functions on Rm

Let S be a finite subset of Rm having n elements. A real valued function k on S is said to be quasiconvex if there exists a quasi-convex function k′ defined on the convex hull co(S) of S such that k = k′ on S. Given a real function ƒ on S, the problem is to find a best quasi-convex approximation g to ƒ in the uniform norm. In this article, the greatest quasi-convex minorant of ƒ is characterized, and the maximal best approximation to ƒ is identified as a shift of the minorant. An algorithm for computing this best approximation is developed and its complexity is analyzed as a function of n when m = 2. The algorithm involves computation of on-line or semidynamic convex hulls. The problem has applications in curve fitting and graphics.