Academic
Publications
A Randomized Algorithm for Weighted Approximation of Points by a Step Function

A Randomized Algorithm for Weighted Approximation of Points by a Step Function,10.1007/978-3-642-17458-2_25,Jin-Yi Liu

A Randomized Algorithm for Weighted Approximation of Points by a Step Function  
BibTex | RIS | RefWorks Download
The problem considered in this paper is: given an integer k > 0 and a set P of n points in the plane each with a corresponding non-negative weight, find a step function f with k steps that minimize the maximum weighted vertical distance between f and all the points in P. We present a randomized algorithm to solve the problem in O(nlogn) expected running time. The bound is obviously optimal for the unsorted input. The previously best known algorithm runs in O(nlog2 n) worst-case time. Another merit of the algorithm is its simplicity. The algorithm is just a randomized implementation of Frederickson and Johnson’s matrix searching technique, and it only exploits a simple data structure.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.