We study approximation algorithms for the following geometric version of the maximum coverage problem: Let P be a set of n weighted points in the plane. We want to place m a * b rectangles such that the sum of the weights of the points in P covered by these rectangles is maximized.For any fixed > 0, we present efficient approximation schemes that can find (1-{ \epsilon})-approximation to the optimal solution.In particular, for m = 1, our algorithm runs in linear time O(n log( 1/{ \epsilon})), improving over the previous result. For m > 1, we present an algorithm that runs in O(n/{ \epsilon}log(1/{ \epsilon})+m(1/{ \epsilon})^(O(min(sqrt(m),1/{ \epsilon}))) time.
Categories: cs.CG