Near-linear time approximation schemes for geometric maximum coverage

Abstract

We study approximation algorithms for the following geometric version of the maximum coverage problem: Let be a set of n weighted points in the plane. Let D represent a planar object, such as a rectangle, or a disk. We want to place m copies of D such that the sum of the weights of the points in covered by these copies is maximized. For any fixed , we present efficient approximation schemes that can find a -approximation to the optimal solution. In particular, for and for the special case where D is a rectangle, our algorithm runs in time , improving on the previous result. For and the rectangular case, our algorithm runs in time. For a more general class of shapes (including disks, polygons with edges), our algorithm runs in time.