An on-line algorithm for fitting straight lines between data ranges

Abstract

Applications often require fitting straight lines to data that is input incrementally. The case where a data range [ α k , ω k ] is received at each t k , t 1 < t 2 < … t n , is considered. An algorithm is presented that finds all the straight lines u = mt + b that pierce each data range, i.e., all pairs ( m, b ) such that α k ≤ mt k + b ≤ ω k for k = 1, … , n . It may be that no single line fits all the ranges, and different alternatives for handling this possibility are considered. The algorithm is on-line, producing the correct partial result after processing the first k ranges for all k < n . For each k , the set of ( m , b ) pairs constitutes a convex polygon in the m - b parameter space, which can be constructed as the intersection of 2 k half-planes. It is shown that the O ( n log n ) half-plane intersection algorithm of Shamos and Hoey can be improved in this special case to O ( n ).