All Approximating Segments for a Sequence of Points

In this paper, we consider the problem of approximat-ing a sequence of n points by a line segment in such a way that the distance of each point from this seg-ment is not greater than a given constant. Further-more, the distance between the first(last) input point and the start(end)-point of the approximating segment must not be greater than the given constant. This is a sub-problem in solving unrestricted line simplifica-tion and minimum-link path problems. We propose an O(n log n) algorithm for computing a representation of these segments and we prove that the lower time com-plexity of finding all such segments (in a specific rep-resentation) is Ω(n log n) on the algebraic computation tree model which means that our algorithm is optimal