Approximation Algorithms for Geometric Maximum Coverage

Abstract

We study the maximum coverage problem for geometric set systems: given a set of points, a set of geometric objects, and a number $k$, select $k$ objects maximizing the number of points inside their union. - We present a polynomial-time approximation algorithm with approximation factor strictly better than $1-1/e$ for any set system with linear 2-shallow cell complexity (or any set system that can be decomposed into a constant number of such set systems). The result also holds for the weighted maximum coverage problem, where objects have weights and we want to select objects with total weight within a given budget. The result applies to many types of geometric objects, including pseudodisks in 2D, fat axis-aligned rectangles in 2D, similar-size fat triangles in 2D, axis-aligned unit cubes in 3D. - For small $k$, we obtain a $(1-\epsilon)$-approximation algorithm more generally for any set system with constant VC dimension, running in time exponential in $\tilde{O}(k/\epsilon)$. This simplifies and improves Badanidiyuru, Kleinberg, and Lee's parameterized approximation scheme [SoCG'12] running in time exponential in $\tilde{O}(k^2/\epsilon^5)$. - A continuous version of the geometric maximum coverage problem asks for $k$ objects maximizing the volume of their union. We give better approximation algorithms for this problem for certain families of objects; e.g., we obtain an EPTAS for fat convex objects in any constant dimension. - We complement our algorithms with several hardness results, e.g., APX-hardness for fat axis-aligned rectangles in 2D, $(1-1/e+\epsilon)$-approximation hardness for axis-aligned boxes in a dimension dependent on $\epsilon$, and a lower bound ruling out $n^{\mathop{\rm poly}(1/\epsilon)}$-time PTASs for the continuous problem for axis-aligned boxes in 3D.