Approximating a set of points by a step function
Let S be a set of n points in the plane. We derive algorithms for approximating S by a step function of size k<n, i.e., by an x -monotone rectilinear polyline R R with k<n horizontal segments. We use the vertical distance to measure the quality of the approximation, i.e., the maximum distance from a point in S to the horizontal segment directly above or below it. We consider two types of problems: min-?, where the goal is to minimize the error for a given number of horizontal segments k and min-#, where the goal is to minimize the number of segments for a given allowed error ?. After O(n) preprocessing time, we solve instances of the latter in O(min{klogn,n}) time per instance. We can then solve the former problem in O(min{n2, nklogn}) time. Both algorithms require O(n) space. Our second contribution is an approximation algorithm for the min-? problem that computes a solution within a factor of 3 of the optimal error for k segments, or with at most the same error as the k-optimal but using 2k?1 segments. Furthermore, experiments on real data show even better results than what is guaranteed by the theoretical bounds. Both approximations run in O(nlogn) time and O(n) space.
approximation algorithms combinatorial optimization visual data reduction curve fitting