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 RR 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{k log n, n}) time per instance. We can then solve the former problem in O (min{n2, nk log n}) 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 (n log n) time and O (n) space.