Efficient piecewise-linear function approximation using the uniform metric
Michael T. Goodrich · 1994
We give an O(nlogn)-time method for finding a best k-link piecewise-linear function approximating an n-point planar data set using the well-known uniform metric to measure the error, ε≥0, of the approximation. Our method is based upon new characterizations of such functions, which we exploit to design an efficient algorithm using a plane sweep in “ε space” followed by several applications of the parametric searching technique. The previous best running time for this problem was O(n2).