Approximation Algorithms for Geometric Maximum Coverage

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\mathrm{/}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-ϵ)$-approximation algorithm more generally for any set system with constant VC dimension, running in time exponential in $\tilde{O}(k\mathrm{/}ϵ)$. This simplifies and improves Badanidiyuru, Kleinberg, and Lee’s parameterized approximation scheme [SoCG’12] running in time exponential in $\tilde{O}(k^2\mathrm{/}{ϵ}^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\mathrm{/}e+ϵ)$-approximation hardness for axis-aligned boxes in a dimension dependent on $ϵ$, and a lower bound ruling out $n^{(1\mathrm{/}ϵ)}$-time PTASs for the continuous problem for axis-aligned boxes in 3D.