We consider the problem of weighted rectilinear approximation on the plane and offer both exact algorithms and heuristics with provable performance bounds. Let S = {(p_i,w_i)} be a set of n points p_i in the plane, with associated distance-modifying weights w_i > 0. We present algorithms for finding the best fit to S among x-monotone rectilinear polylines R with a given number k < n of horizontal segments. We measure the quality of the fit by the greatest weighted vertical distance, i.e., the approximation error is max_(1≤i≤n) w_id_v(p_i,R), where d_v(p_i,R) is the vertical distance from p_i to R. We can solve for arbitrary k optimally in O(n~2) or approximately in O(n log~2 n) time. We also describe a randomized algorithm with an O(n log~2 n) expected running time for the unweighted case and describe how to modify it to handle the weighted case in O(n log~3 n) expected time. All algorithms require O(n) space.
展开▼
