An algorithm for discrete approximation by quasi-convex functions on R-m
Let S be a finite subset of R-m 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 f on S, the problem is to find a best quasi-convex approximation g to f in the uniform norm. In this article, the greatest quasi-convex minorant of f is characterized, and the maximal best approximation to f 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. (C) 2004 Elsevier Ltd. All rights reserved.
algorithm discrete approximation quasi-convex functions convex hulls uniform norm best approximation computational complexity