Linear Time Approximation Schemes for Geometric Maximum Coverage

Abstract

We study approximation algorithms for the following geometric version of the maximum coverage problem: Let $\mathcal{P}$ 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 $\mathcal{P}$ covered by these copies is maximized. For any fixed $\epsilon >0$, we present efficient approximation schemes that can find a $(1-\epsilon )$-approximation to the optimal solution. In particular, for $m=1$ and for the special case where $D$ is a rectangle, our algorithm runs in time $O(n\log (\frac{1}{\epsilon }))$, improving on the previous result. For $m>1$ and the rectangular case, our algorithm runs in $O(\frac{n}{\epsilon }\log (\frac{1}{\epsilon })+\frac{m}{\epsilon }\log m+m(\frac{1}{\epsilon }{)}^{O(\min (\sqrt{m},\frac{1}{\epsilon }))})$ time. For a more general class of shapes (including disks, polygons with $O(1)$ edges), our algorithm runs in $O(n(\frac{1}{\epsilon }{)}^{O(1)}+\frac{m}{\epsilon }\log m+m(\frac{1}{\epsilon }{)}^{O(\min (m,\frac{1}{{\epsilon }^2}))})$ time.

28pages; The conference version arXiv:1505.02591 of this paper was published in COCOON 2015