FITTING POLYGONAL FUNCTIONS TO A SET OF POINTS IN THE PLANE

Given a set of points S = {(x1, y1), (x2, y2), ..., (xN, yN)} in R2 with x1 < x2 < ... < xN, we want to construct a polygonal (i.e., continuous, piecewise linear) function f with a small number of corners (i.e., nondifferentiable points) which fits S well. To measure the quality of f in this regard, we employ two criteria: 1. (i) the number of corners in the graph of f, and 2. (ii) max1≤i≤N|yi - f(xi)| (the Chebyshev error of the fit). We give efficient algorithms to construct a polygonal function f that minimizes (i) (resp. (ii)) under a maximum allowable value of (ii) (resp. (i)), whether or not the comers of f are constrained to be in the set S. A key tool used in designing these algorithms is a linear time algorithm to find the visibility polygon from an edge in a monotone polygon. A variation of one of these algorithms solves the following computational geometry problem in optimal O(N) time: Given N vertical segments in the plane, no two with the same abscissa, find a monotone polygonal curve with the least number of corners which intersects all the segments. © 1991.