  In their seminal work, Mustafa and Ray (2009) showed that a wide class of
geometric set cover (SC) problems admit a PTAS via local search -- this is one
of the most general approaches known for such problems. Their result applies if
a naturally defined "exchange graph" for two feasible solutions is planar and
is based on subdividing this graph via a planar separator theorem due to
Frederickson (1987). Obtaining similar results for the related maximum
k-coverage problem (MC) seems non-trivial due to the hard cardinality
constraint. In fact, while Badanidiyuru, Kleinberg, and Lee (2012) have shown
(via a different analysis) that local search yields a PTAS for two-dimensional
real halfspaces, they only conjectured that the same holds true for dimension
three. Interestingly, at this point it was already known that local search
provides a PTAS for the corresponding set cover case and this followed directly
from the approach of Mustafa and Ray.
  In this work we provide a way to address the above-mentioned issue. First, we
propose a color-balanced version of the planar separator theorem. The resulting
subdivision approximates locally in each part the global distribution of the
colors. Second, we show how this roughly balanced subdivision can be employed
in a more careful analysis to strictly obey the hard cardinality constraint.
More specifically, we obtain a PTAS for any "planarizable" instance of MC and
thus essentially for all cases where the corresponding SC instance can be
tackled via the approach of Mustafa and Ray. As a corollary, we confirm the
conjecture of Badanidiyuru, Kleinberg, and Lee regarding real half spaces in
dimension three. We feel that our ideas could also be helpful in other
geometric settings involving a cardinality constraint.
