EFFICIENT PIECEWISE-LINEAR FUNCTION APPROXIMATION USING THE UNIFORM METRIC

We give an O(n log n)-time method for finding a best k-link piecewise- linear function approximating an n-point planar point set using the we ll-known uniform metric to measure the error, epsilon greater than or equal to 0. Of the approximation. Our method is based upon new charact erizations of such functions, which we exploit to design an efficient algorithm using a plane sweep in ''epsilon space'' followed by several applications of the parametric-searching technique. The previous best running time for this problem was O(n(2)).