Efficient (Piecewise) Linear Minmax Approximation of Digital Signals

In this work efficient geometric algorithms are provided for the linear approximation of digital signals under the uniform norm. Given a set of n points (xi, yi)i=1..n, with xi < xj if i < j, we give a new method to find the optimum linear approximation in O(n). Given also an error bound, we demonstrate how to construct in O(n) a non continuous piecewise solution such that the number k of segments is optimal. Furthermore we show that for such number of segments, the solution that is l∞ optimal can also be found in O(n) provided that n/k = O(1).