An algorithm for l∞ regression with quadratic complexity

Using a few very basic observations, we proposed recently a direct and finite algorithm for the computation of the l(infinity) regression line on a discrete set {(x(i), y(i))}(i)(n) under the assumption that x(1) < x(2) < ... <x(n). In this paper, we extend the algorithm to the case with at least one, possibly multiple y-values for each distinct xi. Our algorithm finds all the regression lines in O(n(2)) operations in the worst-case scenario and improves the existing best-known computational complexity result for this problem, Numerical results on random problems are included.