In this paper, we consider the problem of approximating a sequence of n points by a line segment in such a way that the distance of each point from this segment is not greater than a given constant. Furthermore, the distance between the rst(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 simplication and minimum-link path problems. We propose an O(n logn) algorithm for computing a representation of these segments and we prove that the lower time complexity of nding all such segments (in a specic representation) is (n logn) on the algebraic computation tree model which means that our algorithm is optimal.
['Ghobad Emadi', 'Alireza Zarei']
All Approximating Segments for a Sequence of Points