# Minimum-Membership Geometric Set Cover, Revisited

Sayan Bandyapadhyay Portland State University, USA,
<EMAIL_ADDRESS>William Lochet LIRMM, Université de
Montpellier, CNRS, Montpellier, France<EMAIL_ADDRESS>Saket
Saurabh Institute of Mathematical Sciences, Chennai, India<EMAIL_ADDRESS>Jie Xue New York University Shanghai, China<EMAIL_ADDRESS>
###### Abstract

We revisit a natural variant of the geometric set cover problem, called
minimum-membership geometric set cover (MMGSC). In this problem, the input
consists of a set $S$ of points and a set $\mathcal{R}$ of geometric objects,
and the goal is to find a subset $\mathcal{R}^{*}\subseteq\mathcal{R}$ to
cover all points in $S$ such that the membership of $S$ with respect to
$\mathcal{R}^{*}$, denoted by $\mathsf{memb}(S,\mathcal{R}^{*})$, is
minimized, where $\mathsf{memb}(S,\mathcal{R}^{*})=\max_{p\in
S}|\\{R\in\mathcal{R}^{*}:p\in R\\}|$. We give the first polynomial-time
approximation algorithms for MMGSC in $\mathbb{R}^{2}$. Specifically, we
achieve the following two main results.

  * •

We give the first polynomial-time constant-approximation algorithm for MMGSC
with unit squares. This answers a question left open since the work of
Erlebach and Leeuwen [SODA’08], who gave a constant-approximation algorithm
with running time $n^{O(\mathsf{opt})}$ where $\mathsf{opt}$ is the optimum of
the problem (i.e., the minimum membership).

  * •

We give the first polynomial-time approximation scheme (PTAS) for MMGSC with
halfplanes. Prior to this work, it was even unknown whether the problem can be
approximated with a factor of $o(\log n)$ in polynomial time, while it is
well-known that the minimum-size set cover problem with halfplanes can be
solved in polynomial time.

We also consider a problem closely related to MMGSC, called minimum-ply
geometric set cover (MPGSC), in which the goal is to find
$\mathcal{R}^{*}\subseteq\mathcal{R}$ to cover $S$ such that the ply of
$\mathcal{R}^{*}$ is minimized, where the ply is defined as the maximum number
of objects in $\mathcal{R}^{*}$ which have a nonempty common intersection.
Very recently, Durocher et al. gave the first constant-approximation algorithm
for MPGSC with unit squares which runs in $O(n^{12})$ time. We give a
significantly simpler constant-approximation algorithm with near-linear
running time.

##  1 Introduction

Geometric set cover is one of the most fundamental problems in computational
geometry [2, 3, 5, 7, 9, 15]. In the original setting of the problem, we are
given a set $S$ of points and a set $\mathcal{R}$ of geometric objects, and
our goal is to cover all the points in $S$ using fewest objects in
$\mathcal{R}$. Motivated by various applications, several variants of the
geometric set cover problem have also been studied in literature. In this
paper, we study a natural variant of the geometric set cover problem, called
minimum-membership geometric set cover (MMGSC).

In the MMGSC problem, the input also consists of a set $S$ of points and a set
$\mathcal{R}$ of geometric objects. Similar to the geometric set cover problem
our goal is still to cover all the points in $S$ using the objects in
$\mathcal{R}$. However, we do not care about how many geometric objects we
use. Instead, we want to guarantee that any point in $S$ is not “over
covered”. More precisely, the goal is to find a subset
$\mathcal{R}^{*}\subseteq\mathcal{R}$ to cover all points in $S$ such that the
membership of $S$ with respect to $\mathcal{R}^{*}$, denoted by
$\mathsf{memb}(S,\mathcal{R}^{*})$, is minimized, where
$\mathsf{memb}(S,\mathcal{R}^{*})=\max_{p\in S}|\\{R\in\mathcal{R}^{*}:p\in
R\\}|$.

Kuhn et al. [13], motivated by applications in cellular networks, had
introduced the non-geometric version of the MMGSC problem, say minimum-
membership set cover (MMSC). That is, $S$ is an arbitrary universe with $n$
elements and $\mathcal{R}$ is a collection of subsets of $S$. They showed that
the MMSC problem admits an $O(\log n)$-approximation algorithm, where $n=|S|$.
Furthermore, they complimented the upper bound result by showing, that unless
P$=$NP, the problem cannot be approximated, in polynomial time, by a ratio
less than $\ln n$. Erlebach and van Leeuwen [11], in their seminal work on
geometric coverage problem, considered the geometric version of MMSC, namely
MMGSC, from the view of approximation algorithms. They showed NP-hardness for
approximating the problem with ratio less than $2$ on unit disks and unit
squares, and gave a $5$-approximation algorithm for unit squares provided that
the optimal objective value is bounded by a constant. More precisely, their
algorithm runs in time $n^{O(\mathsf{opt})}$ where $\mathsf{opt}$ is the
optimum of the problem (i.e., the minimum membership). It has remained open
that whether MMGSC with unit squares admits a (truly) polynomial-time
constant-approximation algorithm.

As our first result, we settle this open question by giving a polynomial-time
algorithm for MMGSC with unit squares which achieves a constant approximation
ratio. In fact, our algorithm works for a generalized version of the problem,
in which the point set to be covered can be different from the point set whose
membership is considered.

######  Definition 1.1 (generalized MMGSC).

In the generalized minimum-membership geometric set cover (MMGSC) problem, the
input consists of two sets $S,S^{\prime}$ of points in $\mathbb{R}^{d}$ and a
set $\mathcal{R}$ of geometric objects in $\mathbb{R}^{d}$, and the goal is to
find a subset $\mathcal{R}^{*}\subseteq\mathcal{R}$ to cover all points in $S$
such that $\mathsf{memb}(S^{\prime},\mathcal{R}^{*})$ is minimized. We denote
by $\mathsf{opt}(S,S^{\prime},\mathcal{R})$ the optimum of the problem
instance $(S,S^{\prime},\mathcal{R})$, i.e.,
$\mathsf{opt}(S,S^{\prime},\mathcal{R})=\mathsf{memb}(S^{\prime},\mathcal{R}^{*})$
where $\mathcal{R}^{*}\subseteq\mathcal{R}$ is an optimal solution.

######  Theorem 1.2.

The generalized MMGSC problem with unit squares admits a polynomial-time
constant-approximation algorithm.

Our second result is a polynomial-time approximation scheme (PTAS) for MMGSC
with halfplanes. Prior to this work, it was even unknown whether the problem
can be approximated in polynomial time with a factor of $o(\log n)$, while the
minimum-size set cover problem with halfplanes is polynomial-time solvable.
Again, our PTAS works for the generalized version.

######  Theorem 1.3.

The generalized MMGSC problem with halfplanes admits a PTAS.

The generalized version of MMGSC is interesting because it also generalizes
another closely related problem studied in the literature, called minimum-ply
geometric set cover (MPGSC). The MPGSC problems was introduced by Biedl,
Biniaz and Lubiw [4] as a variant of MMGSC. They observed that in some
applications, e.g. interference reduction in cellular networks, it is
desirable to minimize the membership of every point in the plane, not only
points of $S$. Therefore, in MPGSC, the goal is to find
$\mathcal{R}^{*}\subseteq\mathcal{R}$ to covers $S$ such that the ply of
$\mathcal{R}^{*}$ is minimized, where the ply is defined as the maximum number
of objects in $\mathcal{R}^{*}$ which have a nonempty common intersection.
Observe that MPGSC is a special case of the generalized MMGSC (by letting
$S^{\prime}$ include a point in every face of the arrangement induced by
$\mathcal{R}$). As such, Theorems 1.2 and 1.3 both apply to MPGSC.

Prior to our work, Biedl, Biniaz and Lubiw [4] showed that solving the MPGSC
with a set of axis-parallel unit squares is NP-hard, and gave a polynomial-
time $2$-approximation algorithm for instances in which the optimum (i.e., the
minimum ply) is a constant. Very recently, Durocher, Keil and Mondal [10] gave
the first constant-approximation algorithm for MPGSC with unit squares, which
runs in $O(n^{12})$ time. This algorithm does not extend to other related
settings, such as similarly sized squares or unit disks. Our algorithm derived
from Theorem 1.2 is already much more efficient than the one of [10] (while
also not extend to similarly sized squares or unit disks). However, we observe
that for (only) MPGSC with unit squares, there exists a very simple constant-
approximation algorithm which runs in $\widetilde{O}(n)$ time; here
$\widetilde{O}$ hides logarithmic factors. This simple algorithm directly
extends to any similarly sized fat objects for which a constant-approximation
solution for minimum-size set cover can be computed in polynomial time.
Therefore, we obtain the following result.

######  Theorem 1.4.

The MPGSC problem with unit (or similarly sized) squares/disks admits
constant-approximation algorithms with running time $\widetilde{O}(n)$.

A common ingredient appearing in all of our results is to establish
connections between MMGSC (or MPGSC) and the standard minimum-size geometric
set cover. We show that in certain situations, a minimum-size set cover
(satisfying certain conditions) can be a good approximation in terms of MMGSC.
This reveals the underlying relations between different variants of geometric
set cover problems, and might be of independent interest.

#### Other related work.

Very recently, Mitchell and Pandit [14] proved that MMGSC with rectangles
intersecting a horizontal line or anchored on two horizontal lines is NP-hard
(among other algorithmic and hardness results).

#### Organization.

The rest of the paper is organized as follows. In Section 2, we present our
result for MMGSC with unit squares. In Section 3, we present our result for
MMGSC with halfplanes. The result for MPGSC is given in Section 4. Finally, in
Section 5, we conclude the paper and give some open questions for future
study.

##  2 Constant approximation for unit squares

Let $S,S^{\prime}$ be two sets of points in $\mathbb{R}^{2}$ and $\mathcal{Q}$
be a set of (axis-parallel) unit squares. We want to solve the generalized
MMGSC instance $(S,S^{\prime},\mathcal{Q})$.

###  2.1 Restricting $S$ to a grid cell

First of all, we construct a grid $\varGamma$ consisting of square cells of
side-length 1. For each grid cell $\Box$, we write $S_{\Box}=S\cap\Box$ and
$\mathcal{Q}_{\Box}=\\{Q\in\mathcal{Q}:Q\cap\Box\neq\emptyset\\}$.

######  Lemma 2.1.

Suppose that, for every $\Box\in\varGamma$,
$\mathcal{Q}_{\Box}^{*}\subseteq\mathcal{Q}_{\Box}$ is a $c$-approximation
solution of the generalized MMGSC instance
$(S_{\Box},S^{\prime},\mathcal{Q}_{\Box})$. Then
$\bigcup_{\Box\in\varGamma}\mathcal{Q}_{\Box}^{*}$ is an $O(c)$-approximation
solution of the instance $(S,S^{\prime},\mathcal{Q})$.

###### Proof.

Note that $\bigcup_{\Box\in\varGamma}\mathcal{Q}_{\Box}^{*}$ is a set cover of
$S$, because any point $p\in S$ is contained in a grid cell $\Box$ and thus
$\mathcal{Q}_{\Box}^{*}$ covers $p$. Then we show that for any point
$p^{\prime}\in S^{\prime}$, the number of unit squares in
$\bigcup_{\Box\in\varGamma}\mathcal{Q}_{\Box}^{*}$ containing $p^{\prime}$ is
at most $9c\cdot\mathsf{opt}(S,S^{\prime},\mathcal{Q})$. Suppose the grid cell
containing $p^{\prime}$ is $\Box^{\prime}$. Observe that a unit square
$Q\in\bigcup_{\Box\in\varGamma}\mathcal{Q}_{\Box}^{*}$ contains $p^{\prime}$
only if $Q\in\mathcal{Q}_{\Box}^{*}$ for a grid cell $\Box$ that is either
$\Box^{\prime}$ or one of the 8 grid cells around $\Box^{\prime}$. For each
such cell $\Box$, the number of unit squares in $\mathcal{Q}_{\Box}^{*}$
containing $p^{\prime}$ is at most
$c\cdot\mathsf{opt}(S_{\Box},S^{\prime},\mathcal{Q}_{\Box})$, since
$\mathcal{Q}_{\Box}^{*}$ is a $c$-approximation solution of
$(S_{\Box},S^{\prime},\mathcal{Q}_{\Box})$. Clearly,
$\mathsf{opt}(S_{\Box},S^{\prime},\mathcal{Q}_{\Box})\leq\mathsf{opt}(S,S^{\prime},\mathcal{Q})$.
So there can be at most $9c\cdot\mathsf{opt}(S,S^{\prime},\mathcal{Q})$ unit
squares in $\bigcup_{\Box\in\varGamma}\mathcal{Q}_{\Box}^{*}$ containing
$p^{\prime}$, which implies that
$\bigcup_{\Box\in\varGamma}\mathcal{Q}_{\Box}^{*}$ is a $9c$-approximation
solution of $(S,S^{\prime},\mathcal{Q})$. ∎

###  2.2 Partition the instance using LP

Based on the previous discussion, we will now assume that $S$ is contained in
a grid cell $\Box$ and all unit squares in $\mathcal{Q}$ intersect $\Box$.
Note that the points in $S^{\prime}$ can be everywhere in the plane. We shall
formulate an LP relaxation of the generalized MMGSC instance
$(S,S^{\prime},\mathcal{Q})$. To this end, we first introduce the notion of
fractional set cover. A fractional set cover of a set $A$ of points is a set
$\\{x_{B}\\}_{B\in\mathcal{B}}$ of numbers in $[0,1]$ indexed by a collection
$\mathcal{B}$ of geometric ranges such that $\sum_{B\in\mathcal{B},a\in
B}x_{B}\geq 1$ for all $a\in A$. For another set $A^{\prime}$ of points, we
can define the membership of $A^{\prime}$ with respect to this fractional set
cover $\\{x_{B}\\}_{B\in\mathcal{B}}$ as
$\mathsf{memb}(A^{\prime},\\{x_{B}\\}_{B\in\mathcal{B}})=\max_{a^{\prime}\in
A^{\prime}}\sum_{B\in\mathcal{B},a^{\prime}\in B}x_{B}$. The LP relaxation of
the instance $(S,S^{\prime},\mathcal{Q})$ simply asks for a fractional set
cover of $S$ using the unit squares in $\mathcal{Q}$ that minimizes the
membership of $S^{\prime}$ with respect to it. Specifically, for each unit
square $Q\in\mathcal{Q}$, we create a variable $x_{Q}$. In addition, we create
another variable $y$, which indicates the upper bound for the membership of
$S$ with respect to $\\{x_{Q}\\}_{Q\in\mathcal{Q}}$. We consider the following
linear program.

$\begin{array}[]{rl}&\min\text{ }y\\\\[8.61108pt] \text{s.t. }&0\leq x_{Q}\leq
1\text{ for all $Q\in\mathcal{Q}$,}\\\\[4.30554pt] &\sum_{Q\in\mathcal{Q},p\in
Q}x_{Q}\geq 1\text{ for all $p\in S$,}\\\\[4.30554pt]
&\sum_{Q\in\mathcal{Q},p^{\prime}\in Q}x_{Q}\leq y\text{ for all
$p^{\prime}\in S^{\prime}$.}\end{array}$

We compute an optimal solution $(\\{x_{Q}^{*}\\}_{Q\in\mathcal{Q}},y^{*})$ of
the above linear program using a polynomial-time LP solver. We have the
following observation about the solution.

######  Fact 2.2.

$y^{*}\leq\mathsf{opt}(S,S^{\prime},\mathcal{Q})$.

###### Proof.

Let $\mathcal{Q}^{*}\subseteq\mathcal{Q}$ be an optimal solution. We have
$S\subseteq\bigcup_{Q\in\mathcal{Q}^{*}}$ and
$\mathsf{memb}(S^{\prime},\mathcal{Q}^{*})=\mathsf{opt}(S,S^{\prime},\mathcal{Q})$.
Set $x_{Q}=1$ for $Q\in\mathcal{Q}^{*}$, $X_{Q}=0$ for
$Q\notin\mathcal{Q}^{*}$, and $y=\mathsf{memb}(S^{\prime},\mathcal{Q}^{*})$.
These values satisfy the LP constraints. Therefore, $y^{*}\leq
y=\mathsf{opt}(S,S^{\prime},\mathcal{R})$. ∎

Next, we shall partition the instance $(S,S^{\prime},\mathcal{Q})$ into four
sub-instances according to the LP solution
$(\\{x_{Q}^{*}\\}_{Q\in\mathcal{Q}},y^{*})$. Recall that all points in $S$ are
inside the grid cell $\Box$ and all unit squares in $\mathcal{Q}$ intersect
$\Box$. Let $c_{1},c_{2},c_{3},c_{4}$ be the four corners of $\Box$. We can
partition $\mathcal{Q}$ into
$\mathcal{Q}_{1},\mathcal{Q}_{2},\mathcal{Q}_{3},\mathcal{Q}_{4}$, where
$\mathcal{Q}_{i}$ consists of the unit squares containing $c_{i}$ for
$i\in\\{1,2,3,4\\}$. Also, we partition $S$ into $S_{1},S_{2},S_{3},S_{4}$ in
the following way. For a point $p\in\mathbb{R}^{2}$ and $i\in\\{1,2,3,4\\}$,
define $\delta_{p,i}$ as the sum of $x_{Q}^{*}$ for all $Q\in\mathcal{Q}_{i}$
satisfying $p\in Q$. Then we assign each point $p\in S$ to $S_{i}$, where
$i\in\\{1,2,3,4\\}$ is the index that maximizes $\delta_{p,i}$. Observe the
following fact.

######  Fact 2.3.

For each $i\in\\{1,2,3,4\\}$, we have $\sum_{Q\in\mathcal{Q}_{i},p\in
Q}x_{Q}^{*}\geq\frac{1}{4}$ for all $p\in S_{i}$.

###### Proof.

We have $\sum_{Q\in\mathcal{Q}_{i},p\in Q}x_{Q}^{*}=\delta_{p,i}$ and
$\sum_{i=1}^{4}\delta_{p,i}=\sum_{Q\in\mathcal{Q},p\in Q}x_{Q}^{*}\geq 1$,
because of the LP constraints. Furthermore, $\delta_{p,i}\geq\delta_{p,j}$ for
all $j\in\\{1,2,3,4\\}$, as $p\in S_{i}$. Thus, $\delta_{p,i}\geq\frac{1}{4}$.
∎

We now partition the original instance into
$(S_{1},S^{\prime},\mathcal{Q}_{1}),\dots,(S_{4},S^{\prime},\mathcal{Q}_{4})$.
Consider an index $i\in\\{1,2,3,4\\}$. If we define
$\tilde{x}_{Q}^{*}=4x_{Q}^{*}$ for all $Q\in\mathcal{Q}_{i}$, then the above
fact implies $\sum_{Q\in\mathcal{Q}_{i},p\in Q}\tilde{x}_{Q}^{*}\geq 1$ for
all $p\in S_{i}$. In other words,
$\\{\tilde{x}_{Q}^{*}\\}_{Q\in\mathcal{Q}_{i}}$ is a fractional set cover of
$S_{i}$. Note that
$\mathsf{memb}(S^{\prime},\\{\tilde{x}_{Q}^{*}\\}_{Q\in\mathcal{Q}_{i}})\leq
4y^{*}$, because

$4y^{*}\geq\sum_{Q\in\mathcal{Q},p^{\prime}\in
Q}4x_{Q}^{*}\geq\sum_{Q\in\mathcal{Q}_{i},p^{\prime}\in Q}\tilde{x}_{Q}^{*}$

for all $p^{\prime}\in S$, due to the constraints of the LP. With this
observation, it now suffices to compute a solution for each instance
$(S_{i},S^{\prime},\mathcal{Q}_{i})$ that is a constant-factor approximation
even with respect to the fractional solutions. The union of these solutions is
a set cover of $S=\bigcup_{i=1}^{4}S_{i}$, the membership of $S^{\prime}$ with
respect to it is $O(y^{*})$. A nice property of the instances
$(S_{i},S^{\prime},\mathcal{Q}_{i})$ is that all unit squares in
$\mathcal{Q}_{i}$ contain the same corner $c_{i}$ of $\Box$. In the next
section, we show how to compute the desired approximation solution for such
instances.

###  2.3 The one-corner case

Now consider an instance $(S,S^{\prime},\mathcal{Q})$, where all points in $S$
lie in a grid cell $\Box$ and all unit squares contain the same corner (say
the bottom-left corner) of $\Box$. For a point $p\in\mathbb{R}^{2}$, denote by
$x(p)$ and $y(p)$ the $x$-coordinate and $y$-coordinate of $p$, respectively.
Also, for a unit square $Q\in\mathcal{Q}$, denote by $x(Q)$ and $y(Q)$ the
$x$-coordinate and $y$-coordinate of the top-right corner of $Q$,
respectively. We make two simple observations. The first one shows that the
integral gap of the minimum-size set cover problem in this setting is equal to
1. The second one gives a useful geometric property for unit squares
containing the same corner of $\Box$.

######  Fact 2.4.

Let $S_{0}\subseteq S$ be a subset and $\mathcal{Q}_{0}\subseteq\mathcal{Q}$
be a minimum-size set cover of $S_{0}$. For any fractional set cover
$\\{\hat{x}_{Q}\\}_{Q\in\mathcal{Q}}$ of $S_{0}$, we have
$\sum_{Q\in\mathcal{Q}}\hat{x}_{Q}\geq|\mathcal{Q}_{0}|$.

###### Proof.

For convenience, for a set $A$ of points and a set $\mathcal{B}$ of ranges, we
write $\pi(A,\mathcal{B})$ as the minimum size of a set cover of $A$ using the
ranges in $\mathcal{B}$. Now it suffices to show that
$\sum_{Q\in\mathcal{Q}}\hat{x}_{Q}\geq\pi(S_{0},\mathcal{Q})$ for any
fractional set cover $\\{\hat{x}_{Q}\\}_{Q\in\mathcal{Q}}$ of $S_{0}$. We
apply induction on $\lfloor\sum_{Q\in\mathcal{Q}}\hat{x}_{Q}\rfloor$. When
$\lfloor\sum_{Q\in\mathcal{Q}}\hat{x}_{Q}\rfloor=0$, we must have
$S_{0}=\emptyset$ and the statement trivially holds. Suppose the statement
holds when $\lfloor\sum_{Q\in\mathcal{Q}}\hat{x}_{Q}\rfloor\leq k-1$, and
consider the case $\lfloor\sum_{Q\in\mathcal{Q}}\hat{x}_{Q}\rfloor=k$. Let
$p\in S_{0}$ be the rightmost point in $S_{0}$, i.e., $x(p)\geq x(q)$ for all
$q\in S_{0}$, and $Q_{p}\in\mathcal{Q}$ be the unit square containing $p$ that
maximizes $y(Q_{p})$. For $Q\in\mathcal{Q}$, we define

$\hat{x}_{Q}^{\prime}=\left\\{\begin{array}[]{cc}\hat{x}_{Q}&\text{if }p\notin
Q,\\\ 0&\text{if }p\in Q\text{ and }Q\neq Q_{p},\\\ 1&\text{if
}Q=Q_{p}.\end{array}\right.$

Observe that
$\sum_{Q\in\mathcal{Q}}\hat{x}_{Q}^{\prime}\leq\sum_{Q\in\mathcal{Q}}\hat{x}_{Q}$.
Indeed, since $\\{\hat{x}_{Q}\\}_{Q\in\mathcal{Q}}$ is a fractional set cover
of $S_{0}$, we have $\sum_{Q\in\mathcal{Q},p\in Q}\hat{x}_{Q}\geq
1=\sum_{Q\in\mathcal{Q},p\in Q}\hat{x}_{Q}^{\prime}$. Also,
$\sum_{Q\in\mathcal{Q},p\notin
Q}\hat{x}_{Q}^{\prime}=\sum_{Q\in\mathcal{Q},p\notin Q}\hat{x}_{Q}$ by
definition. Thus,
$\sum_{Q\in\mathcal{Q}}\hat{x}_{Q}^{\prime}\leq\sum_{Q\in\mathcal{Q}}\hat{x}_{Q}$.
As $\lfloor\sum_{Q\in\mathcal{Q}}\hat{x}_{Q}\rfloor=k$, we have
$\lfloor\sum_{Q\in\mathcal{Q}}\hat{x}_{Q}^{\prime}\rfloor\leq k$ and thus
$\lfloor\sum_{Q\in\mathcal{Q}\backslash\\{Q_{p}\\}}\hat{x}_{Q}^{\prime}\rfloor\leq
k-1$. Furthermore, we notice that
$\\{\hat{x}_{Q}^{\prime}\\}_{Q\in\mathcal{Q}}$ is also a fractional set cover
of $S_{0}$. To see this, consider a point $q\in S_{0}$. We have $x(q)\leq
x(p)\leq x(Q_{p})$. If $q\in Q_{p}$, then $\sum_{Q\in\mathcal{Q},q\in
Q}\hat{x}_{Q}^{\prime}\geq 1$. Assume $q\notin Q_{p}$, which implies
$y(q)>y(Q_{p})$ because $x(q)\leq x(Q_{p})$. By the choice of $Q_{p}$, for all
$Q\in\mathcal{Q}$ such that $p\in Q$, we have $y(q)>y(Q)$ and thus $q\notin
Q$. It follows that $\sum_{Q\in\mathcal{Q},q\in
Q}\hat{x}_{Q}^{\prime}=\sum_{Q\in\mathcal{Q},q\in Q}\hat{x}_{Q}\geq 1$. So
$\\{\hat{x}_{Q}^{\prime}\\}_{Q\in\mathcal{Q}}$ is a fractional set cover of
$S_{0}$. Therefore,
$\\{\hat{x}_{Q}^{\prime}\\}_{Q\in\mathcal{Q}\backslash\\{Q_{p}\\}}$ is a
fractional set cover of $S_{0}\backslash Q_{p}$. Using the fact
$\lfloor\sum_{Q\in\mathcal{Q}\backslash\\{Q_{p}\\}}\hat{x}_{Q}^{\prime}\rfloor\leq
k-1$ and our induction hypothesis, we have
$\sum_{Q\in\mathcal{Q}\backslash\\{Q_{p}\\}}\hat{x}_{Q}^{\prime}\geq\pi(S_{0}\backslash
Q_{p},\mathcal{Q}\backslash\\{Q_{p}\\})$. Note that $\pi(S_{0}\backslash
Q_{p},\mathcal{Q}\backslash\\{Q_{p}\\})\geq\pi(S_{0},\mathcal{Q})-1$, simply
because a set cover of $S_{0}\backslash Q_{p}$ together with $Q_{p}$ forms a
set cover of $S_{0}$. As a result,
$\sum_{Q\in\mathcal{Q}\backslash\\{Q_{p}\\}}\hat{x}_{Q}^{\prime}\geq\pi(S_{0},\mathcal{Q})-1$
and hence
$\sum_{Q\in\mathcal{Q}}\hat{x}_{Q}^{\prime}\geq\pi(S_{0},\mathcal{Q})$. Since
$\sum_{Q\in\mathcal{Q}}\hat{x}_{Q}^{\prime}\leq\sum_{Q\in\mathcal{Q}}\hat{x}_{Q}$,
we finally have $\sum_{Q\in\mathcal{Q}}\hat{x}_{Q}\geq\pi(S_{0},\mathcal{Q})$,
which completes the proof. ∎

######  Fact 2.5.

Let $Q^{-},Q,Q^{+}$ be three unit squares all containing the bottom-left
corner of $\Box$ which satisfy $x(Q^{-})\leq x(Q)\leq x(Q^{+})$ and
$y(Q^{-})\geq y(Q)\geq y(Q^{+})$. Then $Q^{-}\cap Q^{+}\subseteq Q$.

###### Proof.

Let $p\in Q^{-}\cap Q^{+}$. The fact $p\in Q^{-}$ implies $x(p)\leq x(Q^{-})$
and $y(Q^{-})-1\leq y(p)$. So we have $x(p)\leq x(Q)$ and $y(Q)-1\leq y(p)$.
On the other hand, the fact $p\in Q^{+}$ implies $x(Q^{+})-1\leq x(p)$ and
$y(p)\leq y(Q^{+})$. So we have $x(Q)-1\leq x(p)$ and $y(p)\leq y(Q)$.
Therefore, $x(Q)-1\leq x(p)\leq x(Q)$ and $y(Q)-1\leq y(p)\leq y(Q)$, which
implies that $p\in Q$. ∎

We say a unit square $Q\in\mathcal{Q}$ is dominated by another unit square
$Q^{\prime}\in\mathcal{Q}$ if $Q\cap\Box\subseteq Q^{\prime}\cap\Box$. A unit
square in $\mathcal{Q}$ is maximal if it is not dominated by any other unit
squares in $\mathcal{Q}$. We denote by
$\mathcal{Q}_{\mathsf{max}}\subseteq\mathcal{Q}$ the set of maximal unit
squares in $\mathcal{Q}$. The following lemma shows that any minimum-size set
cover of $S$ that only uses the unit squares in $\mathcal{Q}_{\mathsf{max}}$
is also a good approximation for the minimum-membership set cover.

######  Lemma 2.6.

Let $\mathcal{Q}^{*}\subseteq\mathcal{Q}$ be a minimum-size set cover of $S$
such that $\mathcal{Q}^{*}\subseteq\mathcal{Q}_{\mathsf{max}}$, and
$\\{x_{Q}\\}_{Q\in\mathcal{Q}}$ be a fractional set cover of $S$. Then
$\mathsf{memb}(S^{\prime},\mathcal{Q}^{*})\leq\mathsf{memb}(S^{\prime},\\{x_{Q}\\}_{Q\in\mathcal{Q}})+2$.

###### Proof.

Suppose $\mathcal{Q}^{*}=\\{Q_{1},\dots,Q_{r}\\}$ where
$x(Q_{1})\leq\cdots\leq x(Q_{r})$. As
$\mathcal{Q}^{*}\subseteq\mathcal{Q}_{\mathsf{max}}$, we must have
$x(Q_{1})<\cdots<x(Q_{r})$ and $y(Q_{1})>\cdots>y(Q_{r})$. Consider a point
$p^{\prime}\in S^{\prime}$. Let $i^{-}\in[r]$ (resp., $i^{+}\in[r]$) be the
smallest (resp., largest) index such that $p^{\prime}\in Q_{i^{-}}$ (resp.,
$p^{\prime}\in Q_{i^{+}}$). By Fact 2.5, we have $p^{\prime}\in Q_{i^{-}}\cap
Q_{i^{+}}\subseteq Q_{i}$ for all $i\in\\{i^{-},\dots,i^{+}\\}$ and thus
$|\\{Q\in\mathcal{Q}^{*}:p^{\prime}\in Q\\}|=i^{+}-i^{-}+1$. It suffices to
show that $\sum_{Q\in\mathcal{Q},p^{\prime}\in Q}x_{Q}\geq i^{+}-i^{-}-1$.

Consider the rectangle
$R=(x(Q_{i^{-}}),x(Q_{i^{+}})]\times(y(Q_{i^{+}}),y(Q_{i^{-}})]$; see Figure
1. Set $S_{0}=S\cap R$ and
$\mathcal{Q}_{0}=\\{Q_{i^{-}+1},\dots,Q_{i^{+}-1}\\}$. Observe that
$\mathcal{Q}_{0}$ covers $S_{0}$, since no unit square in
$\mathcal{Q}^{*}\backslash\mathcal{Q}_{0}$ contains any point in $S_{0}$. We
claim that $\mathcal{Q}_{0}\subseteq\mathcal{Q}$ is a minimum-size set cover
of $S_{0}$. Indeed, since $x(Q_{i^{-}})<\cdots<x(Q_{i^{+}})$ and
$y(Q_{i^{-}})>\cdots>y(Q_{i^{+}})$, the points in $S\backslash S_{0}$ are all
covered by the unit squares $Q_{1},\dots,Q_{i^{-}}$ and
$Q_{i^{+}},\dots,Q_{r}$. If there exists a set cover
$\mathcal{Q}_{0}^{\prime}\subseteq\mathcal{Q}$ of $S_{0}$ such that
$|\mathcal{Q}_{0}^{\prime}|<|\mathcal{Q}_{0}|$, then
$\mathcal{Q}_{0}^{\prime}$ together with
$Q_{1},\dots,Q_{i^{-}},Q_{i^{+}},\dots,Q_{r}$ form a set cover of $S$ whose
size is smaller than $\mathcal{Q}^{*}$, contradicting with the fact that
$\mathcal{Q}^{*}$ is a minimum-size set cover of $S$. Therefore,
$\mathcal{Q}_{0}\subseteq\mathcal{Q}$ is a minimum-size set cover of $S_{0}$.
Now for each $Q\in\mathcal{Q}$, define $\hat{x}_{Q}=x_{Q}$ if $Q\cap
R\neq\emptyset$ and $\hat{x}_{Q}=0$ if $Q\cap R=\emptyset$. As
$\\{x_{Q}\\}_{Q\in\mathcal{Q}}$ is a fractional set cover of $S$, for each
$p\in S_{0}$, we have $\sum_{Q\in\mathcal{Q},p\in Q}x_{Q}\geq 1$, which
implies $\sum_{Q\in\mathcal{Q},p\in Q}\hat{x}_{Q}\geq 1$ because $p\in R$ and
thus $\hat{x}_{Q}=x_{Q}$ for all $Q\in\mathcal{Q}$ such that $p\in Q$. So
$\\{\hat{x}_{Q}\\}_{Q\in\mathcal{Q}}$ is a fractional set cover of $S_{0}$. By
Fact 2.4, we then have

$\sum_{Q\in\mathcal{Q}}\hat{x}_{Q}\geq|\mathcal{Q}_{0}|=i^{+}-i^{-}-1.$ (1)

Figure 1: Illustrating the rectangle $R$.

Next, we observe that $x(Q_{i^{-}})\leq x(Q)\leq x(Q_{i^{+}})$ and
$y(Q_{i^{-}})\geq y(Q)\geq y(Q_{i^{+}})$ for any unit square $Q\in\mathcal{Q}$
such that $Q\cap R\neq\emptyset$. Let $Q\in\mathcal{Q}$ and assume $Q\cap
R\neq\emptyset$. The inequalities $x(Q_{i^{-}})\leq x(Q)$ and $y(Q)\geq
y(Q_{i^{+}})$ follow directly from the fact $Q\cap R\neq\emptyset$. If
$x(Q)>x(Q_{i^{+}})$, then $Q$ dominates $Q_{i^{+}}$, contradicting the fact
$Q_{i^{+}}\in\mathcal{Q}_{\mathsf{max}}$. Similarly, if $y(Q_{i^{-}})<y(Q)$,
then $Q$ dominates $Q_{i^{-}}$, contradicting the fact
$Q_{i^{-}}\in\mathcal{Q}_{\mathsf{max}}$. Thus, $x(Q_{i^{-}})\leq x(Q)$ and
$y(Q_{i^{-}})\geq y(Q)$. By Fact 2.5, we have $p^{\prime}\in Q_{i^{-}}\cap
Q_{i^{+}}\subseteq Q$ for all $Q\in\mathcal{Q}$ such that $Q\cap
R\neq\emptyset$. Thus, $\hat{x}_{Q}=0$ for all $Q\in\mathcal{Q}$ such that
$p^{\prime}\notin Q$, which implies

$\sum_{Q\in\mathcal{Q},p^{\prime}\in
Q}x_{Q}\geq\sum_{Q\in\mathcal{Q},p^{\prime}\in
Q}\hat{x}_{Q}=\sum_{Q\in\mathcal{Q}}\hat{x}_{Q}.$ (2)

Combining Equations 1 and 2, we have $\sum_{Q\in\mathcal{Q},p^{\prime}\in
Q}x_{Q}\geq i^{+}-i^{-}-1$. ∎

Using the above lemma, now it suffices to compute a minimum-size set cover of
$S$ using the unit squares in $\mathcal{Q}_{\mathsf{max}}$. It is well-known
that in this setting, the minimum-size set cover problem can be solved in
polynomial time (or even near-linear time) using a greedy algorithm, because
the unit squares in $\mathcal{Q}$ are in fact equivalent to southwest
quadrants; see for example [1]. Thus, we can compute in polynomial time a set
cover $\mathcal{Q}^{*}\subseteq\mathcal{Q}$ of $S$ such that
$\mathsf{memb}(S^{\prime},\mathcal{Q}^{*})\leq\mathsf{memb}(S^{\prime},\\{x_{Q}\\}_{Q\in\mathcal{Q}})+2$
for any fractional set cover $\\{x_{Q}\\}_{Q\in\mathcal{Q}}$ of $S$.

###  2.4 Putting everything together

Recall that at the end of Section 2.2, we have four generalized MMGSC
instances $(S_{1},S^{\prime},\mathcal{Q}_{1}),$
$\dots,(S_{4},S^{\prime},\mathcal{Q}_{4})$. Also, for each
$i\in\\{1,\dots,4\\}$, we have a fractional set cover
$\\{\tilde{x}_{Q}^{*}\\}_{Q\in\mathcal{Q}_{i}}$ of $S_{i}$ such that
$\mathsf{memb}(S^{\prime},\\{\tilde{x}_{Q}^{*}\\}_{Q\in\mathcal{Q}_{i}})\leq
4y^{*}\leq 4\cdot\mathsf{opt}(S,S^{\prime},\mathcal{Q})$. By the discussion in
Section 2.3, for each $i\in\\{1,\dots,4\\}$, we can compute in polynomial time
a set cover $\mathcal{Q}_{i}^{*}\subseteq\mathcal{Q}_{i}$ of $S_{i}$
satisfying that
$\mathsf{memb}(S^{\prime},\mathcal{Q}_{i}^{*})\leq\mathsf{memb}(S^{\prime},\\{\tilde{x}_{Q}^{*}\\}_{Q\in\mathcal{Q}_{i}})+2$.
Set $\mathcal{Q}^{*}=\bigcup_{i=1}^{4}\mathcal{Q}_{i}^{*}$. As
$S=\bigcup_{i=1}^{4}S_{i}$, $\mathcal{Q}^{*}$ is a set cover of $S$.
Furthermore, we have

$\begin{array}[]{rl}\mathsf{memb}(S^{\prime},\mathcal{Q}^{*})&\leq\
\sum_{i=1}^{4}\mathsf{memb}(S^{\prime},\mathcal{Q}_{i}^{*})\\\\[4.30554pt]
&\leq\
\sum_{i=1}^{4}\mathsf{memb}(S^{\prime},\\{\tilde{x}_{Q}^{*}\\}_{Q\in\mathcal{Q}_{i}})+8\\\\[4.30554pt]
&\leq\ 16y^{*}+8\\\\[4.30554pt] &\leq\
16\cdot\mathsf{opt}(S,S^{\prime},\mathcal{Q})+8.\end{array}$

If $\mathsf{opt}(S,S^{\prime},\mathcal{Q})>0$, then $\mathcal{Q}^{*}$ is a
constant-approximation solution. The case
$\mathsf{opt}(S,S^{\prime},\mathcal{Q})=0$ can be easily solved by picking all
unit squares in $\mathcal{Q}$ that do not contain any points in $S^{\prime}$.
Therefore, we obtain a constant-approximation algorithm for the case where $S$
is contained in a grid cell. Further combining this with Lemma 2.1, we
conclude the following. See 1.2

##  3 Polynomial-time approximation scheme for halfplanes

Let $S,S^{\prime}$ be two sets of points in $\mathbb{R}^{2}$ and $\mathcal{H}$
be a set of halfplanes. We want to solve the generalized MMGSC instance
$(S,S^{\prime},\mathcal{H})$. Set $n=|S|+|S^{\prime}|+|\mathcal{H}|$.

In order to describe our algorithm, we first need to introduce some basic
notions about halfplanes. The normal vector (or normal for short) of a
halfplane $H$ is the unit vector perpendicular to the bounding line of $H$
whose direction is to the interior of $H$, that is, if the equation of $H$ is
$ax+by+c\geq 0$ where $a^{2}+b^{2}=1$, then its normal is $\vec{v}=(a,b)$. For
two nonzero vectors $\vec{u}$ and $\vec{v}$ in the plane, we denote by
$\mathsf{ang}(\vec{u},\vec{v})$ the clockwise ordered angle from $\vec{u}$ to
$\vec{v}$, i.e., the angle between $\vec{u}$ and $\vec{v}$ that is to the
clockwise of $\vec{u}$ and to the counter-clockwise of $\vec{v}$. For two
halfplanes $H$ and $J$, we write
$\mathsf{ang}(H,J)=\mathsf{ang}(\vec{u},\vec{v})$ where $\vec{u}$ (resp.,
$\vec{v}$) is the normal of $H$ (resp., $J$). For a set $\mathcal{R}$ of
halfplanes, we use $\bigcap\mathcal{R}$ and $\bigcup\mathcal{R}$ to denote the
intersection and the union of all halfplanes in $\mathcal{R}$, respectively.
We say a halfplane $H\in\mathcal{R}$ is redundant in $\mathcal{R}$ if
$\bigcap\mathcal{R}=\bigcap(\mathcal{R}\backslash\\{H\\})$. We say
$\mathcal{R}$ is irreducible if every halfplane in $\mathcal{R}$ is not
redundant. The complement region of $\mathcal{R}$ refers to the closure of
$\mathbb{R}^{2}\backslash\bigcup\mathcal{R}$, which is always a convex polygon
(possibly unbounded). The following simple facts about halfplanes will be used
throughout the section.

######  Fact 3.1.

Let $\mathcal{R}$ be an irreducible set of halfplanes such that
$\bigcup\mathcal{R}\neq\mathbb{R}^{2}$. Then the following two properties
hold.

  1. (i)

For any halfplane $H\in\mathcal{R}$ and another halfplane $H^{\prime}$
different from $H$, we have that
$\bigcup\mathcal{R}\neq\bigcup\mathcal{R}^{\prime}$, where
$\mathcal{R}^{\prime}=(\mathcal{R}\backslash\\{H\\})\cup\\{H^{\prime}\\}$.

  2. (ii)

If the halfplanes in $\mathcal{R}$ has a nonempty intersection, i.e.,
$\bigcap\mathcal{R}\neq\emptyset$, then we can write
$\mathcal{R}=\\{H_{1},\dots,H_{t}\\}$ such that
$0<\mathsf{ang}(H_{1},H_{2})<\mathsf{ang}(H_{1},H_{3})<\cdots<\mathsf{ang}(H_{1},H_{t})<\pi$.

###### Proof.

We first prove property (i). As $\mathcal{R}$ is irreducible and
$\bigcup\mathcal{R}\neq\mathbb{R}^{2}$, $H$ contributes a segment (or a ray)
$\sigma$ on the boundary of the complement region of $\mathcal{R}$. If
$\bigcup\mathcal{R}=\bigcup\mathcal{R}^{\prime}$, then $\sigma$ is also a
segment on the boundary of the complement region of $\mathcal{R}^{\prime}$.
Furthermore, the side of $\sigma$ corresponding to the interior of
$\bigcup\mathcal{R}$ coincides the side of $\sigma$ corresponding to the
interior of $\bigcup\mathcal{R}^{\prime}$, since $\mathcal{R}$ and
$\mathcal{R}^{\prime}$ share the same complement region. Therefore, we must
have $H\in\mathcal{R}^{\prime}$ in order to have $\sigma$ on the boundary of
the complement region of $\mathcal{R}^{\prime}$. This contradicts the
assumption $H^{\prime}\neq H$.

Then we prove property (ii). Let $p\in\bigcap\mathcal{R}$ and
$q\in\mathbb{R}^{2}\backslash(\bigcup\mathcal{R})$. Without loss of
generality, assume the line $\overline{pq}$ is vertical and $p$ is below $q$.
Now every halfplane $H\in\mathcal{R}$ contains $p$ but does not contain $q$.
Thus, the equation of $H$ is $y\leq kx+b$ for some $k,b\in\mathbb{R}^{2}$.
Sort the halfplanes in $\mathcal{R}$ as $H_{1},\dots,H_{t}$ such that if
$y\leq k_{i}x+b_{i}$ is the equation of $H_{i}$, then $k_{1}\geq\dots\geq
k_{t}$. Clearly,
$0\leq\mathsf{ang}(H_{1},H_{2})\leq\mathsf{ang}(H_{1},H_{3})\leq\cdots\leq\mathsf{ang}(H_{1},H_{t})<\pi$.
Now observe that $\mathsf{ang}(H_{i},H_{i+1})>0$. Indeed, if
$\mathsf{ang}(H_{i},H_{i+1})=0$, then either $H_{i}\subseteq H_{i+1}$ or
$H_{i+1}\subseteq H_{i}$, which contradicts the assumption that
$\mathcal{R}=\\{H_{1},\dots,H_{t}\\}$ is irreducible. As such, we have the
inequality
$0<\mathsf{ang}(H_{1},H_{2})<\mathsf{ang}(H_{1},H_{3})<\cdots<\mathsf{ang}(H_{1},H_{t})<\pi$.
∎

######  Fact 3.2.

Let $H_{1},\dots,H_{t}$ be halfplanes such that

$0<\mathsf{ang}(H_{1},H_{2})<\mathsf{ang}(H_{1},H_{3})<\cdots<\mathsf{ang}(H_{1},H_{t})\leq\pi.$

Then the following two properties hold.

  1. (i)

If $H_{1}\cup H_{t}\neq\mathbb{R}^{2}$, then neither $H_{1}$ nor $H_{t}$ is
redundant in $\\{H_{1},\dots,H_{t}\\}$.

  2. (ii)

If $\\{H_{1},\dots,H_{t}\\}$ is irreducible, then
$\bigcap_{i=1}^{t}H_{i}=H_{1}\cap H_{t}$.

###### Proof.

We first prove property (i). Without loss of generality, it suffices to show
$H_{1}$ is not redundant in $\\{H_{1},\dots,H_{t}\\}$ and we can assume the
equation of $H_{1}$ is $y\geq 0$. The boundary line $\ell$ of $H_{1}$ is
defined by the equation $y=0$. As $0<\mathsf{ang}(H_{1},H_{i})<\pi$ for every
$i\in\\{2,\dots,t-1\\}$, $H_{i}$ contains the $x=+\infty$ end of $\ell$ but
does not contain the $x=-\infty$ end of $\ell$. If
$\mathsf{ang}(H_{1},H_{t})<\pi$, then $H_{t}$ also does not contain the
$x=-\infty$ end of $\ell$, which implies
$\ell\nsubseteq\bigcup_{i=2}^{t}H_{i}$ and thus $H_{1}$ is not redundant in
$\\{H_{1},\dots,H_{t}\\}$. If $\mathsf{ang}(H_{1},H_{t})=\pi$, then the
equation of $H_{t}$ is $y\leq c$ for some $c\in\mathbb{R}$. Note that $c<0$,
as $H_{1}\cup H_{t}\neq\mathbb{R}^{2}$. Thus, $H_{t}$ does not intersect
$\ell$ and thus $H_{1}$ is not redundant in $\\{H_{1},\dots,H_{t}\\}$.

Then we prove property (ii). It suffices to show that $H_{1}\cap
H_{t}\subseteq H_{i}$ for all $i\in\\{2,\dots,t-1\\}$. Without loss of
generality, we only need to consider the case $i=2$. We first notice that
$\mathsf{ang}(H_{1},H_{2})>0$. Indeed, if $\mathsf{ang}(H_{1},H_{2})=0$, then
either $H_{1}\subseteq H_{2}$ or $H_{2}\subseteq H_{1}$, which contradicts the
fact that $\\{H_{1},\dots,H_{t}\\}$ is irreducible. For the same reason,
$\mathsf{ang}(H_{2},H_{t})>0$. Thus,
$\mathsf{ang}(H_{1},H_{2})<\mathsf{ang}(H_{1},H_{t})$. If
$\mathsf{ang}(H_{1},H_{t})=\pi$, then $H_{1}$ and $H_{t}$ are halfplanes with
opposite direction, which implies either $H_{1}\cap H_{t}=\emptyset$ or
$H_{1}\cup H_{t}=\mathbb{R}^{2}$. In the former case, we directly have
$H_{1}\cap H_{t}\subseteq H_{2}$. In the latter case, we have $t=2$ (and thus
$H_{1}\cap H_{t}\subseteq H_{2}$ trivially holds), for otherwise
$H_{2},\dots,H_{t-1}$ are all redundant in $\\{H_{1},\dots,H_{t}\\}$,
contradicting the assumption that $\\{H_{1},\dots,H_{t}\\}$ is irreducible. So
it suffice to consider the case $\mathsf{ang}(H_{1},H_{t})<\pi$. Now
$\mathsf{ang}(H_{1},H_{2})<\mathsf{ang}(H_{1},H_{t})<\pi$. Without loss of
generality, assume the equation of $H_{2}$ is $x\geq 0$. Then the equation of
$H_{1}$ is $y\geq kx+b$ for some $k,b\in\mathbb{R}$ and the equation of
$H_{t}$ is $y\leq k^{\prime}x+b^{\prime}$ for some
$k^{\prime},b^{\prime}\in\mathbb{R}$. Let $p$ be the intersection of the lines
$y=kx+b$ and $y=k^{\prime}x+b^{\prime}$. Note that $H_{1}\cup H_{t}$ covers
all points with $x$-coordinates greater than or equal to $p$. It follows that
the $x$ coordinate of $p$ is positive, for otherwise $H_{2}\subseteq H_{1}\cup
H_{t}$, which contradicts the fact that $\\{H_{1},\dots,H_{t}\\}$ is
irreducible. Also notice that the area $H_{1}\cap H_{t}$ is entirely to the
right of $p$, and is thus contained in $H_{2}$. ∎

###  3.1 An $n^{O(\mathsf{opt})}$-time exact algorithm

In this section, we show how to compute an (exact) optimal solution of the
instance $(S,S^{\prime},\mathcal{H})$ in $n^{O(\mathsf{opt})}$ time. It
suffices to solve a decision problem: given an integer $k\geq 0$, find a
subset $\mathcal{Z}\subseteq\mathcal{H}$ which covers $S$ and satisfies
$\mathsf{memb}(S^{\prime},\mathcal{Z})\leq k$ or decide that such a subset
does not exist. As long as this problem can be solved in $n^{O(k)}$ time, by
trying $k=1,\dots,|\mathcal{H}|$, we can finally compute an optimal solution
of $(S,S^{\prime},\mathcal{H})$ in $n^{O(\mathsf{opt})}$ time. In what
follows, a valid solution of $(S,S^{\prime},\mathcal{H})$ refers to a subset
$\mathcal{Z}\subseteq\mathcal{H}$ which covers $S$ and satisfies
$\mathsf{memb}(S^{\prime},\mathcal{Z})\leq k$.

Let $\Delta$ be a sufficiently large number such that $S\cup
S^{\prime}\subseteq[-\Delta,\Delta]^{2}$. For convenience, we add to
$\mathcal{H}$ four dummy halfplanes with equations $y\leq-\Delta$,
$y\geq\Delta$, $x\leq-\Delta$, and $x\geq\Delta$. As these dummy halfplanes
does not contain any points in $S\cup S^{\prime}$, including them in
$\mathcal{H}$ does not change the problem. We say a set of halfplanes is
regular if it is irreducible and its complement region is nonempty and
bounded. We have the following simple observation.

######  Fact 3.3.

If $(S,S^{\prime},\mathcal{H})$ has a valid solution, then either it has a
regular valid solution or it has a valid solution that covers the entire plane
$\mathbb{R}^{2}$.

###### Proof.

Consider a valid solution $\mathcal{Z}\subseteq\mathcal{H}$ of
$(S,S^{\prime},\mathcal{H})$. We shall create another valid solution which
either is regular or covers $\mathbb{R}^{2}$. First, we add the four dummy
halfplanes to $\mathcal{Z}$ and let $\mathcal{Z}^{\prime}\supseteq\mathcal{Z}$
denote the resulting set. Then $\mathcal{Z}^{\prime}$ covers $S$ and
$\mathsf{memb}(S^{\prime},\mathcal{Z}^{\prime})=\mathsf{memb}(S^{\prime},\mathcal{Z})$.
So $\mathcal{Z}^{\prime}$ is also a valid solution. Next, we obtain an
irreducible subset $\mathcal{Z}^{\prime\prime}\subseteq\mathcal{Z}^{\prime}$
which has the same complement region as $\mathcal{Z}^{\prime}$ by keeping
removing redundant halfplanes from $\mathcal{Z}^{\prime}$. Now
$\mathcal{Z}^{\prime\prime}$ still covers $S$ and
$\mathsf{memb}(S^{\prime},\mathcal{Z}^{\prime\prime})\leq\mathsf{memb}(S^{\prime},\mathcal{Z}^{\prime})$,
which implies that $\mathcal{Z}^{\prime\prime}$ is also a valid solution. If
$\bigcup\mathcal{Z}^{\prime\prime}=\mathbb{R}^{2}$, we are done. Otherwise,
the complement region of $\mathcal{Z}^{\prime\prime}$ is nonempty.
Furthermore, the complement region of $\mathcal{Z}^{\prime\prime}$ is the same
as that of $\mathcal{Z}^{\prime}$, where the latter is bounded because the
four dummy halfplanes are all in $\mathcal{Z}^{\prime}$. Therefore, the
complement region of $\mathcal{Z}^{\prime\prime}$ is bounded. This implies
$\mathcal{Z}^{\prime\prime}$ is regular, because
$\bigcup\mathcal{Z}^{\prime\prime}$ is irreducible. ∎

If $(S,S^{\prime},\mathcal{H})$ has a valid solution that covers
$\mathbb{R}^{2}$, then it also has an irreducible valid solution that covers
$\mathbb{R}^{2}$, which is of size at most $3$ by Helly’s theorem. Therefore,
in this case, we can solve the problem in $n^{O(1)}$ time by simply
enumerating all subsets of $\mathcal{H}$ of size at most $3$. Otherwise, by
the above fact, it suffices to check whether there exists a regular valid
solution of $(S,S^{\prime},\mathcal{H})$. In what follows, we assume
$(S,S^{\prime},\mathcal{H})$ has a regular valid solution and show how to find
such a solution in $n^{O(k)}$ time. If our algorithm does not find a regular
valid solution at the end, we can conclude its non-existence. Let
$\mathcal{Z}\subseteq\mathcal{H}$ be a (unknown) regular valid solution of
$(S,S^{\prime},\mathcal{H})$. By definition, the complement region of
$\mathcal{Z}$ is nonempty, and is a (bounded) convex polygon. Consider the
arrangement $\mathcal{A}$ of the boundary lines of the halfplanes in
$\mathcal{H}$. This arrangement has $O(n^{2})$ faces, among which at least one
face is contained in the complement region of $\mathcal{Z}$. We simply guess
such a face. By making $O(n^{2})$ guesses, we can assume that we know a face
$F$ in the complement region of $\mathcal{Z}$. Then we take a point $p$ in the
interior of $F$, which is also in the interior of the complement region of
$\mathcal{Z}$.

Now the problem becomes finding a regular valid solution of
$(S,S^{\prime},\mathcal{H})$ whose complement region contains $p$. Therefore,
we can remove from $\mathcal{H}$ all halfplanes that contain $p$. Now the
complement region of any subset of $\mathcal{H}$ contains $p$. We say a convex
polygon $\varGamma$ is $\mathcal{H}$-compatible if each edge $e$ of
$\varGamma$ is a portion of the boundary line of some halfplane
$H\in\mathcal{H}$ such that $\varGamma\cap H=e$ (or equivalently $H$ does not
contain $\varGamma$). Note that the complement region of a regular valid
solution is an $\mathcal{H}$-compatible convex polygon $\varGamma$ which
satisfies (i) no point in $S$ lies in the interior of $\varGamma$ and (ii) for
any $k+1$ edges $e_{1},\dots,e_{k+1}$ of $\varGamma$, the intersection
$\bigcap_{i=1}^{k+1}H(e_{i})$ does not contain any point in $S^{\prime}$; here
$H(e)\in\mathcal{H}$ denotes the halfplane whose boundary line containing $e$
and $\varGamma\cap H=e$. On the other hand, every $\mathcal{H}$-compatible
convex polygon satisfying conditions (i) and (ii) is the complement region of
a regular valid solution of $(S,S^{\prime},\mathcal{H})$, which is just the
set of halfplanes corresponding to the edges of $\varGamma$. With this
observation, it suffices to find an $\mathcal{H}$-compatible convex polygon
$\varGamma$ satisfying the two conditions. The follow fact can be used to
simplify condition (ii).

######  Fact 3.4.

If there exist $t$ edges $e_{1},\dots,e_{t}$ of an $\mathcal{H}$-compatible
convex polygon $\varGamma$ with $(\bigcap_{i=1}^{t}H(e_{i}))\cap
S^{\prime}\neq\emptyset$, then there exist $t$ consecutive edges
$f_{1},\dots,f_{t}$ of $\varGamma$ with $(\bigcap_{i=1}^{t}H(f_{i}))\cap
S^{\prime}\neq\emptyset$.

###### Proof.

Set $\mathcal{R}=\\{H(e_{1}),\dots,H(e_{t})\\}$ and assume
$(\bigcap\mathcal{R})\cap S^{\prime}\neq\emptyset$, which implies
$\bigcap\mathcal{R}\neq\emptyset$. Note that the set of halfplanes
corresponding to the edges of $\varGamma$ are irreducible, because $\varGamma$
is $\mathcal{H}$-compatible and thus the interior of each edge $e$ of
$\varGamma$ can only be covered by the halfplane $H(e)$. In particular,
$\mathcal{R}$ is irreducible. Also, $\bigcup\mathcal{R}\neq\mathbb{R}^{2}$ by
our assumption $\bigcup\mathcal{H}\neq\mathbb{R}^{2}$. Therefore, by (ii) of
Fact 3.1, there exist $e^{-},e^{+}\in\\{e_{1},\dots,e_{t}\\}$ such that
$\mathsf{ang}(H(e^{-}),H(e_{i}))\leq\mathsf{ang}(H(e^{-}),H(e^{+}))<\pi$ for
all $i\in[t]$. Now we go clockwise along the boundary of $\varGamma$ from
$e^{-}$ to $e^{+}$, and let $E$ be the set of edges of $\varGamma$ we visit
(including $e^{-}$ and $e^{+}$). Clearly, $e_{i}\in E$ for all $i\in[t]$ and
thus $|E|\geq t$. Furthermore,
$0<\mathsf{ang}(H(e^{-}),H(e))<\mathsf{ang}(H(e^{-}),H(e^{+}))<\pi$ for all
$e\in E\backslash\\{e^{-},e^{+}\\}$. Define $\mathcal{R}^{\prime}=\\{H(e):e\in
E\\}$. Since $\mathcal{R}$ and $\mathcal{R}^{\prime}$ are both irreducible, we
can apply (ii) of Fact 3.2 to deduce $\bigcap\mathcal{R}=H(e^{-})\cap
H(e^{+})=\bigcap\mathcal{R}^{\prime}$, which implies
$(\bigcap\mathcal{R}^{\prime})\cap S^{\prime}\neq\emptyset$. Finally, because
$E$ consists of consecutive edges of $\varGamma$ and $|E|\geq t$, there exist
$f_{1},\dots,f_{t}\in E$ which are $t$ consecutive edges of $\varGamma$. We
have $\bigcap\mathcal{R}^{\prime}\subseteq\bigcap_{i=1}^{t}H(f_{i})$ and thus
$(\bigcap_{i=1}^{t}H(f_{i}))\cap S^{\prime}\neq\emptyset$. ∎

By the above fact, we only need to find an $\mathcal{H}$-compatible convex
polygon $\varGamma$ which satisfies (i) no point in $S$ lies in the interior
of $\varGamma$ and (ii) $(\bigcap_{i=1}^{k+1}H(e_{i}))\cap
S^{\prime}\neq\emptyset$ for any $k+1$ consecutive edges $e_{1},\dots,e_{k+1}$
of $\varGamma$. For convenience, we say $\varGamma$ is well-behaved if it
satisfies conditions (i) and (ii). Next, we reduce this problem to a shortest-
cycle problem in a (weighted) directed graph $G$ as follows. Let $\mathcal{L}$
denote the set of boundary lines of halfplanes in $\mathcal{H}$. We consider
every segment $s$ in the plane which is on some line $\ell\in\mathcal{L}$ and
satisfies that each endpoint of $s$ is the intersection point of $\ell$ and
another line in $\mathcal{L}$. We use $\varPhi$ to denote the set of these
segments. Note that $|\varPhi|=O(n^{3})$, as $\varPhi$ contains $O(n^{2})$
segments on each line $\ell\in\mathcal{L}$. Clearly, the edges of an
$\mathcal{H}$-compatible convex polygon are all segments in $\varPhi$.
Consider a segment $\phi\in\varPhi$. Recall that the point $p$ is the interior
of $F$, which is a face of the arrangement $\mathcal{A}$. Thus, no line in
$\mathcal{L}$ goes through $p$. It follows that for every segment
$\phi\in\varPhi$, the two endpoints of $\phi$ and $p$ form a triangle
$\Delta_{\phi}$. If $p\rightarrow a\rightarrow b$ is the clockwise ordering of
the three vertices of $\Delta_{\phi}$ from $p$, then we call $a$ the left
endpoint of $\phi$ and call $b$ the right endpoint of $\phi$. Clearly,
$\mathsf{ang}(\overrightarrow{pa},\overrightarrow{pb})<\pi$. The vertices of
the graph $G$ to be constructed are one-to-one corresponding to the
$(k+1)$-tuples $(\phi_{0},\phi_{1},\dots,\phi_{k})\in\varPhi^{k+1}$ which
satisfy the following three conditions.

  1. 1.

The left endpoint of $\phi_{i}$ is the right endpoint of $\phi_{i-1}$ for all
$i\in[k]$. Below we use $a_{i}$ to denote the left endpoint of $\phi_{i}$
(i.e., the right endpoint of $\phi_{i-1}$). This condition guarantees that the
segments $\phi_{0},\phi_{1},\dots,\phi_{k}$ form a polygonal chain of $k+1$
pieces.

  2. 2.

$\mathsf{ang}(\overrightarrow{a_{i-1}a_{i}},\overrightarrow{a_{i}a_{i+1}})\leq\pi$
for all $i\in[k]$. This condition guarantees that the chain formed by
$\phi_{0},\phi_{1},\dots,\phi_{k}$ is clockwise convex, in the sense that when
we go along the chain from $a_{0}$ to $a_{k+1}$, we always turn right at the
vertices of the chain. Figure 2 shows a chain satisfying this condition (and
also condition 1).

  3. 3.

$S\cap(\bigcup_{i=0}^{k}\Delta_{\phi_{i}})\subseteq\bigcup_{i=0}^{k}\phi_{i}$
and $(\bigcap_{i=0}^{k}H(\phi_{i}))\cap S^{\prime}=\emptyset$.

Figure 2: Illustrating the conditions for a vertex of $G$.

Intuitively, the $(k+1)$-tuple corresponding to each vertex of $G$ represents
a possible choice of $k+1$ consecutive edges of the $\mathcal{H}$-compatible
convex polygon we are looking for. For two vertices
$v=(\phi_{0},\phi_{1},\dots,\phi_{k})$ and
$v^{\prime}=(\phi_{0}^{\prime},\phi_{1}^{\prime},\dots,\phi_{k}^{\prime})$
such that
$(\phi_{1},\dots,\phi_{k})=(\phi_{0}^{\prime},\phi_{1}^{\prime},\dots,\phi_{k-1}^{\prime})$,
we add a directed edge from $v$ to $v^{\prime}$ with weight
$\mathsf{ang}(\overrightarrow{pa},\overrightarrow{pb})$, where $a$ is the left
endpoint of $\phi_{0}$ and $b$ is the left endpoint of
$\phi_{0}^{\prime}=\phi_{1}$ (which is also the right endpoint of $\phi_{0}$
by condition 1 above). Note that the weight of every edge of $G$ is positive,
since the two endpoints of every $\phi\in\varPhi$ and $p$ form a triangle
$\Delta_{\phi}$. The key observation is the following lemma.

######  Lemma 3.5.

There exists a well-behaved $\mathcal{H}$-compatible convex polygon containing
$p$ iff the (weighted) length of a shortest cycle in $G$ is exactly $2\pi$.

###### Proof.

We first observe that the (weighted) length of any cycle in $G$ is a multiple
of $2\pi$ and is at least $2\pi$. For a vertex
$v=(\phi_{0},\phi_{1},\dots,\phi_{k})$ of $G$, we denote by $a_{v}$ the left
endpoint of $\phi_{0}$. Consider a cycle $(v_{0},v_{1},\dots,v_{r})$ in $G$
where $v_{r}=v_{0}$. By the construction of $G$, the length of the cycle
$(v_{0},\dots,v_{r})$ is
$\sum_{i=0}^{r-1}\mathsf{ang}(\overrightarrow{pa_{v_{i}}},\overrightarrow{pa_{v_{i+1}}})$,
which is a multiple of $2\pi$ since
$\overrightarrow{pa_{v_{0}}}=\overrightarrow{pa_{v_{r}}}$. Furthermore, as the
weight of every edge of $G$ is positive, the length of the cycle is greater
than 0 and thus is at least $2\pi$. With this observation, it now suffices to
show that there exists a well-behaved $\mathcal{H}$-compatible convex polygon
containing $p$ iff there exists a cycle in $G$ of length exactly $2\pi$.

For the “if” part, assume there exists a cycle $(v_{0},v_{1},\dots,v_{r})$ in
$G$ of length exactly $2\pi$, where $v_{r}=v_{0}$. By the construction of $G$,
there exist $\phi_{0},\phi_{1},\dots,\phi_{r-1}\in\varPhi$ such that
$v_{i}=(\phi_{i},\dots,\phi_{i+k})$ for any $i\geq 0$; here for convenience,
we define $\phi_{i}=\phi_{i\text{ mod }r}$ for any $i\geq r$. Let $a_{i}$
denote the left endpoint of $\phi_{i}$. As the length of
$(v_{0},v_{1},\dots,v_{r})$ is $2\pi$, we have
$\sum_{i=0}^{r-1}\mathsf{ang}(\overrightarrow{pa_{i}},\overrightarrow{pa_{i+1}})=2\pi$.
Therefore, the points $a_{0},a_{1},\dots,a_{r-1}$ are located around $p$ in
clockwise order, and the segments $\phi_{0},\phi_{1},\dots,\phi_{r-1}$ enclose
a simple polygon $\varGamma$ containing $p$. We have
$\varGamma=\bigcup_{i=0}^{r-1}\Delta_{\phi_{i}}$. Recall the three conditions
for defining the vertices of $G$. As $(\phi_{i},\dots,\phi_{i+k})$ is a vertex
of $G$ for every $i$, condition 2 guarantees the convexity of $\varGamma$.
Furthermore, since $p\notin H(\phi_{i})$, which implies that $\varGamma$ and
$H(\phi_{i})$ are on the opposite sides of $\phi_{i}$, i.e., $\varGamma\cap
H(\phi_{i})=\phi_{i}$. Therefore, $\varGamma$ is an $\mathcal{H}$-compatible
convex polygon. It suffices to verify that $\varGamma$ is well-behaved. Note
that
$S\cap\varGamma=S\cap(\bigcup_{i=0}^{r-1}\Delta_{\phi_{i}})=\bigcup_{i=0}^{r-1}(S\cap(\bigcup_{j=i}^{i+k}\Delta_{\phi_{j}}))$.
By condition 3, we have
$S\cap(\bigcup_{j=i}^{i+k}\Delta_{\phi_{j}})\subseteq\bigcup_{j=i}^{i+k}\phi_{j}$
for any $i$, which implies
$S\cap\varGamma\subseteq\bigcup_{i=0}^{r-1}\phi_{i}$, i.e., no point in $S$
lies in the interior of $\varGamma$. Again by condition 3,
$(\bigcup_{j=i}^{i+k}H(\phi_{j}))\cap S^{\prime}=\emptyset$ for any $i$. Thus,
$\varGamma$ is well-behaved.

For the “only if” part, assume there exists a well-behaved
$\mathcal{H}$-compatible convex polygon $\varGamma$ containing $p$. Suppose
$\phi_{0},\phi_{1},\dots,\phi_{r-1}$ are the edges of $\varGamma$ in clockwise
order. These edges are segments in $\varPhi$ since $\varGamma$ is
$\mathcal{H}$-compatible. Same as before, we define $\phi_{i}=\phi_{i\text{
mod }r}$ for any $i\geq r$. Now for any $i\geq 0$, the $(k+1)$-tuple
$(\phi_{i},\dots,\phi_{i+k})$ represents $k+1$ consecutive edges of
$\varGamma$. Based on the fact that $\varGamma$ is a well-behaved
$\mathcal{H}$-compatible convex polygon containing $p$, one can easily check
that $(\phi_{i},\dots,\phi_{i+k})$ satisfies conditions 1, 2, 3 for defining
the vertices of $G$. First, condition 1 clearly holds. By the convexity of
$\varGamma$, we then have condition 2. To see condition 3, note that
$\varGamma$ is $\mathcal{H}$-compatible, and thus the halfplanes
$H(\phi_{i}),\dots,H(\phi_{i+k})$ do not intersect the interior of
$\varGamma$. But $\bigcup_{j=i}^{i+k}\Delta_{\phi_{j}}$ is contained in
$\varGamma$. Because $\varGamma$ is well-behaved, every point in
$S\cap\varGamma$ lies on the boundary of $\varGamma$, and thus
$S\cap\bigcup_{j=i}^{i+k}\Delta_{\phi_{j}}\subseteq\bigcup_{j=i}^{i+k}\phi_{j}$.
The emptiness of $(\bigcap_{j=i}^{i+k}H(\phi_{j}))\cap S^{\prime}$ also
follows from the fact that $\varGamma$ is well-behaved. Therefore, condition 3
holds. It follows that $(\phi_{i},\dots,\phi_{i+k})$ is a vertex of $G$, which
we denote by $v_{i}$. By the construction of $G$, there is an edge between
$v_{i}$ and $v_{i+1}$ for any $i\geq 0$. Since $v_{r}=v_{0}$,
$(v_{0},v_{1},\dots,v_{r})$ is a cycle in $G$. If we use $a_{i}$ to denote the
left endpoint of $\phi_{i}$ (which is also the right endpoint of
$\phi_{i-1}$), then $a_{0},a_{1},\dots,a_{r-1}$ are the vertices of
$\varGamma$ in clockwise order. The length of the cycle
$(v_{0},v_{1},\dots,v_{r})$ is then
$\sum_{i=0}^{r-1}\mathsf{ang}(\overrightarrow{pa_{i}},\overrightarrow{pa_{i+1}})=2\pi$.
∎

Based on the above lemma, it suffices to compute a shortest cycle in $G$,
which can be done by standard algorithms (e.g., Dijkstra) in polynomial time
in the size of $G$. Note that $G$ has $n^{O(k)}$ vertices. Therefore, we
obtain an $n^{O(k)}$-time algorithm for computing a set cover
$\mathcal{Z}\subseteq\mathcal{H}$ of $S$ satisfying
$\mathsf{memb}(S^{\prime},\mathcal{Z})\leq k$, if such a set cover exists. By
iteratively trying $k=1,\dots,|\mathcal{H}|$, we can solve the MMGSC problem
with halfplanes in $n^{O(\mathsf{opt})}$ time.

###  3.2 An algorithm with constant additive error

In this section, we show how to compute in polynomial time an approximation
solution $\mathcal{Z}\subseteq\mathcal{H}$ of the instance
$(S,S^{\prime},\mathcal{H})$ with constant additive error, that is,
$\mathsf{memb}(S^{\prime},\mathcal{Z})=\mathsf{opt}(S,S^{\prime},\mathcal{H})+O(1)$.
If $\bigcup\mathcal{H}=\mathbb{R}^{2}$, then by Helly’s theorem, there exist
$H_{1},H_{2},H_{3}\in\mathcal{H}$ such that $H_{1}\cup H_{2}\cup
H_{3}=\mathbb{R}^{2}$. In this case, we can take $\\{H_{1},H_{2},H_{3}\\}$ as
our solution, which clearly has constant additive error. So assume
$\bigcup\mathcal{H}\neq\mathbb{R}^{2}$. Our algorithm is in the spirit of
local search. However, different from most local-search algorithms which
improve the “quality” of the solution in each step (via local modifications),
our algorithm does not care about the quality (i.e., membership), and instead
focuses on shrinking the complement region of the solution. Formally, for two
sets $\mathcal{Z}$ and $\mathcal{Z}^{\prime}$, we write
$\mathcal{Z}\prec\mathcal{Z}^{\prime}$ if
$\bigcup\mathcal{Z}\subsetneq\bigcup\mathcal{Z}^{\prime}$, and
$\mathcal{Z}\preceq\mathcal{Z}^{\prime}$ if
$\bigcup\mathcal{Z}\subseteq\bigcup\mathcal{Z}^{\prime}$. We define the
following notion of “locally (non-)improvable” solutions.

######  Definition 3.6.

A subset $\mathcal{Z}\subseteq\mathcal{H}$ is $k$-expandable if there exists
$\mathcal{Z}^{\prime}\subseteq\mathcal{H}$ such that
$|\mathcal{Z}\backslash\mathcal{Z}^{\prime}|=|\mathcal{Z}^{\prime}\backslash\mathcal{Z}|\leq
k$ and $\mathcal{Z}\prec\mathcal{Z}^{\prime}$. A subset of $\mathcal{H}$ is
$k$-stable if it is not $k$-expandable.

In other words, $\mathcal{Z}\subseteq\mathcal{H}$ is $k$-expandable (resp.,
$k$-stable) if we can (resp., cannot) replace $k$ halfplanes in $\mathcal{Z}$
with other $k$ halfplanes in $\mathcal{H}$ to shrink the complement region of
$\mathcal{Z}$. We are interested in subsets $\mathcal{Z}\subseteq\mathcal{H}$
that are minimum-size set covers of $S$ and are $k$-stable. Such a set can be
constructed via the standard local-search procedure.

######  Lemma 3.7.

A minimum-size set cover $\mathcal{Z}\subseteq\mathcal{H}$ of $S$ that is
$k$-stable can be computed in $n^{O(k)}$ time.

###### Proof.

The standard set cover problem for halfplanes is polynomial-time solvable. So
we can compute a minimum-size set cover $\mathcal{Z}\subseteq\mathcal{H}$ of
$S$ in $n^{O(1)}$ time. To further obtain a $k$-stable one, we keep doing the
following procedure. Whenever there exists
$\mathcal{Z}^{\prime}\subseteq\mathcal{H}$ such that
$|\mathcal{Z}\backslash\mathcal{Z}^{\prime}|=|\mathcal{Z}^{\prime}\backslash\mathcal{Z}|\leq
k$ and $\mathcal{Z}\prec\mathcal{Z}^{\prime}$, we update $\mathcal{Z}$ to
$\mathcal{Z}^{\prime}$. During this procedure, the size of $\mathcal{Z}$ does
not change and the complement region of $\mathcal{Z}$ shrinks. So
$\mathcal{Z}$ is always a minimum-size set cover of $S$. Furthermore, as the
complement region of $\mathcal{Z}$ shrinks in every step, the procedure will
finally terminate. At the end, $\mathcal{Z}$ is not $k$-expandable and is thus
$k$-stable. This proves the correctness of our algorithm. To see it takes
$n^{O(k)}$ time, we show that (i) we terminate in $O(n)$ steps and (ii) each
step can be implemented in $n^{O(k)}$ time.

For (i), the key observation is that every halfplane $H\in\mathcal{H}$ can be
removed from $\mathcal{Z}$ at most once. Formally, we denote by
$\mathcal{Z}_{i}$ the set $\mathcal{Z}$ after the $i$-th step of the
procedure, and thus the original $\mathcal{Z}$ is $\mathcal{Z}_{0}$. Let
$P_{i}$ be the complement region of $\mathcal{Z}_{i}$. Suppose
$H\in\mathcal{Z}_{i-1}$ and $H\notin\mathcal{Z}_{i}$. We claim that
$H\notin\mathcal{Z}_{j}$ for all $j>i$. Assume $H\in\mathcal{Z}_{j}$ for some
$j>i$. Since $\mathcal{Z}_{j}$ is a minimum-size set cover of $S$, $H$ is not
redundant in $\mathcal{Z}_{j}$ and thus one edge $e$ of $P_{j}$ is defined by
$H$, i.e., $e$ is a segment on the boundary line of $H$. Note that $e$ is also
a portion of the boundary of $P_{i-1}$, because $H\in\mathcal{Z}_{i-1}$ and
$P_{j}\subseteq P_{i-1}$. It follows that $e$ is a portion of the boundary of
$P_{i}$, since $P_{j}\subseteq P_{i}\subseteq P_{i-1}$. But this cannot be the
case, as $H\notin\mathcal{Z}_{i}$. Thus, $H\notin\mathcal{Z}_{j}$ for all
$j>i$. Now for every index $i\geq 1$, there exists at least one halfplane
$H\in\mathcal{H}$ such that $H\in\mathcal{Z}_{i-1}$ and
$H\notin\mathcal{Z}_{i}$, simply because
$|\mathcal{Z}_{i-1}|=|\mathcal{Z}_{i}|$ and
$\mathcal{Z}_{i-1}\neq\mathcal{Z}_{i}$. We then charge the $i$-th step to this
halfplane $H$. By the above observation, each halfplane is charged at most
once. Therefore, the procedure terminates in at most $n$ steps. To see (ii),
observe that in each step, the number of
$\mathcal{Z}^{\prime}\subseteq\mathcal{H}$ satisfying
$|\mathcal{Z}\backslash\mathcal{Z}^{\prime}|=|\mathcal{Z}^{\prime}\backslash\mathcal{Z}|\leq
k$ is bounded by $n^{O(k)}$, and these sets can be enumerated in $n^{O(k)}$
time. So each step can be implemented in $n^{O(k)}$ time. As a result, the
entire algorithm terminates in $n^{O(k)}$ time. ∎

Our key observation is that any minimum-size set cover of $S$ that is
$k$-stable has additive error at most $2$ in terms of MMGSC, even for $k=1$.

######  Lemma 3.8.

If $\mathcal{Z}\subseteq\mathcal{H}$ is a minimum-size set cover of $S$ that
is $1$-stable, then we have
$|\mathcal{Z}|\leq\mathsf{opt}(S,S^{\prime},\mathcal{H})+2$.

###### Proof.

Consider a point $p\in S^{\prime}$. We show that
$\mathsf{memb}(p,\mathcal{Z}^{\prime})\geq\mathsf{memb}(p,\mathcal{Z})-2$ for
any set cover $\mathcal{Z}^{\prime}\subseteq\mathcal{H}$ of $S$. Let
$\mathcal{Z}(p)\subseteq\mathcal{Z}$ consist of all halfplanes in
$\mathcal{Z}$ that contain $p$. As $\bigcap\mathcal{Z}(p)\neq\emptyset$, by
(ii) of Fact 3.1 and the assumption $\bigcup\mathcal{H}\neq\mathbb{R}^{2}$, we
have $\mathcal{Z}(p)=\\{H_{1},\dots,H_{r}\\}$ such that
$0<\mathsf{ang}(H_{1},H_{2})<\mathsf{ang}(H_{1},H_{3})<\cdots<\mathsf{ang}(H_{1},H_{r})<\pi$.
Let $S_{0}\subseteq S$ consist of points contained in
$\bigcup_{i=2}^{r-1}H_{i}$ but not contained in any other halfplanes in
$\mathcal{Z}$, and $\mathcal{Z}_{0}^{\prime}\subseteq\mathcal{Z}^{\prime}$
consist of halfplanes that contain at least one point in $S_{0}$. Note that
$|\mathcal{Z}_{0}^{\prime}|\geq r-2$, for otherwise
$(\mathcal{Z}\backslash\\{H_{2},\dots,H_{r-1}\\})\cup\mathcal{Z}_{0}^{\prime}$
is a set cover of $S$ of size strictly smaller than $\mathcal{Z}$, which
contradicts the fact that $\mathcal{Z}$ is a minimum-size set cover of $S$. We
shall show that every halfplane in $\mathcal{Z}_{0}^{\prime}$ contains $p$ and
thus

$\mathsf{memb}(p,\mathcal{Z}^{\prime})\geq\mathsf{memb}(p,\mathcal{Z}_{0}^{\prime})=|\mathcal{Z}_{0}^{\prime}|\geq
r-2=\mathsf{memb}(p,\mathcal{Z})-2.$

Consider a halfplane $H^{\prime}\in\mathcal{Z}_{0}^{\prime}$. We want to show
$p\in H^{\prime}$. By the construction of $\mathcal{Z}_{0}^{\prime}$,
$H^{\prime}$ contains a point $q\in S_{0}$. Furthermore, by the construction
of $S_{0}$, $q$ is contained in $\bigcup_{i=2}^{r-1}H_{i}$ but not contained
in any halfplane in $\mathcal{Z}\backslash\\{H_{2},\dots,H_{r-1}\\}$. In
particular, $q\notin H_{1}$ and $q\notin H_{r}$, which implies $H^{\prime}\neq
H_{1}$ and $H^{\prime}\neq H_{r}$. We observe that
$\\{H_{1},H_{r},H^{\prime}\\}$ is irreducible. Clearly, $H^{\prime}$ is not
redundant in $\\{H_{1},H_{r},H^{\prime}\\}$, as it contains $q$ while $H_{1}$
and $H_{r}$ do not contain $q$. If $H_{1}$ is redundant in
$\\{H_{1},H_{r},H^{\prime}\\}$, then
$\mathcal{Z}\preceq(\mathcal{Z}\backslash\\{H_{1}\\})\cup\\{H^{\prime}\\}$.
Since $\mathcal{Z}$ is irreducible and $H^{\prime}\neq H_{1}$, by (i) of Fact
3.1, this implies
$\mathcal{Z}\prec(\mathcal{Z}\backslash\\{H_{1}\\})\cup\\{H^{\prime}\\}$,
which contradicts the fact that $\mathcal{Z}$ is $1$-stable. So $H_{1}$ is not
redundant in $\\{H_{1},H_{r},H^{\prime}\\}$. For the same reason, $H_{r}$ is
also not redundant in $\\{H_{1},H_{r},H^{\prime}\\}$. Thus,
$\\{H_{1},H_{r},H^{\prime}\\}$ is irreducible.

In what follows, we complete the proof by showing that either $p\in
H^{\prime}$ or $\mathcal{Z}$ is $1$-expandable. As the latter is false (for
$\mathcal{Z}$ is $1$-stable), this implies $p\in H^{\prime}$. If
$\mathsf{ang}(H_{1},H^{\prime})<\mathsf{ang}(H_{1},H_{r})$, by the
irreducibility of $\\{H_{1},H_{r},H^{\prime}\\}$ and (ii) of Fact 3.2, we have
$H_{1}\cap H^{\prime}\cap H_{r}=H_{1}\cap H_{r}$, which implies $H_{1}\cap
H_{r}\subseteq H^{\prime}$ and thus $p\in H_{1}\cap H_{r}\subseteq
H^{\prime}$. If $\mathsf{ang}(H_{1},H^{\prime})=\mathsf{ang}(H_{1},H_{r})$,
then either $H^{\prime}\subseteq H_{r}$ or $H_{r}\subseteq H^{\prime}$. Note
that the former is not true as $q\in H^{\prime}$ but $q\notin H_{r}$. Thus, we
have $p\in H_{r}\subseteq H^{\prime}$. It suffices to consider the case
$\mathsf{ang}(H_{1},H^{\prime})>\mathsf{ang}(H_{1},H_{r})$. In this case, we
show that $\mathcal{Z}$ is $1$-expandable. Since
$q\in\bigcup_{i=2}^{r-1}H_{i}$, there exists $H\in\\{H_{2},\dots,H_{r-1}\\}$
which contains $q$. Now
$\mathsf{ang}(H_{1},H)<\mathsf{ang}(H_{1},H_{r})<\mathsf{ang}(H_{1},H^{\prime})$,
which implies $\mathsf{ang}(H,H_{r})<\mathsf{ang}(H,H^{\prime})$ and
$\mathsf{ang}(H^{\prime},H_{1})<\mathsf{ang}(H^{\prime},H)$. We further
distinguish two cases, $\mathsf{ang}(H,H^{\prime})\leq\pi$ and
$\mathsf{ang}(H,H^{\prime})\geq\pi$ (which are in fact symmetric). Assume
$\mathsf{ang}(H,H^{\prime})\leq\pi$. Figure 3 shows the situation of the
points $p,q$ and the halfplanes $H,H^{\prime},H_{1},H_{r}$ this case. As
$\mathsf{ang}(H,H_{r})<\mathsf{ang}(H,H^{\prime})$, by (ii) of Fact 3.2, if
$\\{H,H_{r},H^{\prime}\\}$ is irreducible, then $H\cap H_{r}\cap
H^{\prime}=H\cap H^{\prime}$. But $H\cap H_{r}\cap H^{\prime}\neq H\cap
H^{\prime}$, because $q\in H\cap H^{\prime}$ and $q\notin H_{r}$. Thus,
$\\{H,H_{r},H^{\prime}\\}$ is reducible. Note that $H\cup
H^{\prime}\neq\mathbb{R}^{2}$, since $\bigcup\mathcal{H}\neq\mathbb{R}^{2}$ by
our assumption. So by (i) of Fact 3.2, neither $H$ nor $H^{\prime}$ is
redundant in $\\{H,H_{r},H^{\prime}\\}$. It follows that $H_{r}$ is redundant
in $\\{H,H_{r},H^{\prime}\\}$, because $\\{H,H_{r},H^{\prime}\\}$ is
reducible. Therefore,
$\mathcal{Z}\preceq(\mathcal{Z}\backslash\\{H_{r}\\})\cup\\{H^{\prime}\\}$.
Since $\mathcal{Z}$ is irreducible and $H^{\prime}\neq H_{r}$, by (i) of Fact
3.1, we have
$\mathcal{Z}\prec(\mathcal{Z}\backslash\\{H_{r}\\})\cup\\{H^{\prime}\\}$,
i.e., $\mathcal{Z}$ is $1$-expandable. The other case
$\mathsf{ang}(H,H^{\prime})\geq\pi$ is similar. In this case,
$\mathsf{ang}(H^{\prime},H)\leq\pi$. Using the fact
$\mathsf{ang}(H^{\prime},H_{1})<\mathsf{ang}(H^{\prime},H)$ and the same
argument as above, we can show that
$\mathcal{Z}\prec(\mathcal{Z}\backslash\\{H_{1}\\})\cup\\{H^{\prime}\\}$,
i.e., $\mathcal{Z}$ is $1$-expandable. ∎

Figure 3: Illustration of the proof of Lemma 3.8.

Using Lemma 3.7, we can compute a $1$-stable minimum-size set cover
$\mathcal{Z}\subseteq\mathcal{H}$ of $S$ in $n^{O(1)}$ time. Then by Lemma
3.8, $\mathcal{Z}$ is an approximation solution for the MMGSC instance
$(S,S^{\prime},\mathcal{H})$ with additive error $2$. This gives us a
polynomial-time approximation algorithm for MMGSC with halfplanes with $O(1)$
additive error.

###  3.3 Putting everything together

Our PTAS can be obtained by directly combining the algorithms in Sections 3.1
and 3.2. Let $c=O(1)$ be the additive error of the algorithm in Section 3.2.
We first run the algorithm in Section 3.2 to obtain a solution
$\mathcal{Z}\subseteq\mathcal{H}$. If
$|\mathcal{Z}|\geq\frac{1+\varepsilon}{\varepsilon}\cdot c$, then

$\frac{|\mathcal{Z}|}{\mathsf{opt}(S,S^{\prime},\mathcal{H})}\leq\frac{|\mathcal{Z}|}{|\mathcal{Z}|-c}\leq
1+\varepsilon.$

In this case, $\mathcal{Z}$ is already a $(1+\varepsilon)$-approximation
solution. Otherwise, $|\mathcal{Z}|<\frac{1+\varepsilon}{\varepsilon}\cdot c$
and thus
$\mathsf{opt}(S,S^{\prime},\mathcal{H})<\frac{1+\varepsilon}{\varepsilon}\cdot
c$. We can then run the algorithm in Section 3.1 to compute an optimal
solution in $n^{O(1/\varepsilon)}$ time. So we conclude the following. See 1.3

##  4 Minimum-ply geometric set cover

In this section, we give a very simple constant-approximation algorithm for
minimum-ply geometric set cover with unit squares. The technique can be
applied to the problem with any similarly-sized geometric objects in
$\mathbb{R}^{2}$.

Let $(S,\mathcal{Q})$ be an MPGSC instance. As in Section 2, we first apply
the grid techinique. We construct a grid $\varGamma$ consisting of square
cells of side-length 1. For each grid cell $\Box$, write $S_{\Box}=S\cap\Box$
and $\mathcal{Q}_{\Box}=\\{Q\in\mathcal{Q}:Q\cap\Box\neq\emptyset\\}$. The key
observation is the following.

######  Lemma 4.1.

Suppose that, for every $\Box\in\varGamma$,
$\mathcal{Q}_{\Box}^{*}\subseteq\mathcal{Q}_{\Box}$ is a $c$-approximation
solution of the minimum-size geometric set cover instance
$(S_{\Box},\mathcal{Q}_{\Box})$. Then
$\bigcup_{\Box\in\varGamma}\mathcal{Q}_{\Box}^{*}$ is an $O(c)$-approximation
solution of the MPGSC instance $(S,\mathcal{Q})$.

###### Proof.

Let $\gamma=\mathsf{ply}(\bigcup_{\Box\in\varGamma}\mathcal{Q}_{\Box}^{*})$
and $p\in\mathbb{R}^{2}$ be a point contained in $\gamma$ unit squares in
$\bigcup_{\Box\in\varGamma}\mathcal{Q}_{\Box}^{*}$. Consider the grid cell
$\Box_{p}$ containing $p$ and define $\mathcal{C}$ as the set of $3\times 3$
grid cells centered at $\Box_{p}$. Note that all unit squares containing $p$
belong to $\bigcup_{\Box\in\mathcal{C}}\mathcal{Q}_{\Box}^{*}$. So we have
$|\bigcup_{\Box\in\mathcal{C}}\mathcal{Q}_{\Box}^{*}|\geq\gamma$ and
$|\max_{\Box\in\mathcal{C}}\mathcal{Q}_{\Box}^{*}|\geq\gamma/9$. Therefore,
there exists $\Box\in\varGamma$ such that
$|\mathcal{Q}_{\Box}^{*}|\geq\gamma/9$. As $\mathcal{Q}_{\Box}^{*}$ is a
$c$-approximation solution of the minimum-size set cover instance
$(S_{\Box},\mathcal{Q}_{\Box})$, we know that any subset of
$\mathcal{Q}_{\Box}$ that covers $S_{\Box}$ has size at least $\gamma/(9c)$.
It follows that any subset of $\mathcal{Q}$ that covers $S$ must include at
least $\gamma/(9c)$ unit squares in $\mathcal{Q}_{\Box}$. Note that each of
these unit squares contains a corner of $\Box$. Thus, at least one corner of
$\Box$ is contained in $\gamma/(36c)$ such unit squares, which implies that
the ply of any solution is at least $\gamma/(36c)$. As a result,
$\bigcup_{\Box\in\varGamma}\mathcal{Q}_{\Box}^{*}$ is an $O(c)$-approximation
solution of the MPGSC instance $(S,\mathcal{Q})$. ∎

Note that the argument in the above proof can be extended to any similarly-
size fat objects in any fixed dimension. Here a set of geometric objects are
similarly-size fat objects if there exist constants $\alpha,\beta>0$ such that
every object in the set contains a ball of radius $\alpha$ and is contained in
a ball of radius $\beta$.

######  Theorem 4.2.

For any class $\mathcal{C}$ of similarly sized fat objects in
$\mathbb{R}^{d}$, if the minimum-size geometric set cover problem with
$\mathcal{C}$ admits a constant-approximation algorithm with running time
$T(n)$ for a function $T$ satisfying $T(a+b)\geq T(a)+T(b)$, then the MPGSC
problem with $\mathcal{C}$ also admits a constant-approximation algorithm with
running time $T(n)$.

###### Proof.

Let $(S,\mathcal{R})$ be an MPGSC instance where
$\mathcal{R}\subseteq\mathcal{C}$. We use the above grid technique to
decompose the input instance $(S,\mathcal{R})$ into a set
$\\{(S_{\Box},\mathcal{R}_{\Box})\\}$ of instances. Then apply the algorithm
for minimum-size geometric set cover problem with $\mathcal{C}$ to compute
constant-approximation (with respect to size) solutions
$\mathcal{R}_{\Box}^{*}\subseteq\mathcal{R}_{\Box}$. By Lemma 4.1,
$\bigcup_{\Box\in\varGamma}\mathcal{R}_{\Box}^{*}$ is a constant-approximation
solution of the MPGSC instance $(S,\mathcal{R})$. If the algorithm for
minimum-size set cover runs in $T(n)$ time, then our algorithm also takes
$T(n)$ time, as long as the function $T$ satisfies $T(a+b)\geq T(a)+T(b)$. ∎

See 1.4

###### Proof.

The $\widetilde{O}(n)$-time constant-approximation algorithms for minimum-size
set cover with similarly sized squares/disks are well-known. For similarly
sized squares, see for example [1]. For similarly sized disks, see for example
[2, 7]. Applying Theorem 4.2 directly yields $\widetilde{O}(n)$-time constant-
approximation algorithms for MPGSC with unit squares and unit disks. ∎

##  5 Conclusion

In this paper, we revisited natural variants of the classical geometric set
cover problem, the minimum-membership geometric set cover (MMGSC) problem and
the minimum-ply geometric set cover (MPGSC). We presented a polynomial-time
constant-approximation algorithm for MMGSC with unit squares, a PTAS for MMGSC
with halfplanes, and a simple constant-approximation algorithm for MPGSC with
unit squares (or unit disks) that runs in near-linear time. Our algorithms is
to establish connections between MMGSC/MPGSC and the standard minimum-size
geometric set cover, which might be of independent interest.

Next, we give some open questions for future study on this topic. First, our
algorithm for MMGSC with unit squares heavily relies on the geometry of unit
squares, and thus cannot be generalized to other settings such as similarly
sized squares or unit disks (while our algorithm for MPGSC can). So it is
interesting to consider the problem with these ranges. Second, it is still not
clear whether the MMGSC problem with halfplanes is NP-hard or not. Thus, an
important question is to settle the complexity of this problem. Finally, the
classical geometric set cover problem has been recently studied in dynamic
settings [1, 6, 8, 12], where points/ranges can be inserted and deleted.
Naturally, one can also study the dynamic version of MMGSC and MPGSC.

## Acknowledgements

The authors would like to thank Qizheng He, Daniel Lokshtanov, Rahul Saladi,
Subhash Suri, and Haitao Wang for helpful discussions about the problems, and
thank the anonymous reviewers for their detailed comments, which help
significantly improve the writing of the paper.

## References

  * [1] Pankaj Agarwal, Hsien-Chih Chang, Subhash Suri, Allen Xiao, and Jie Xue.  Dynamic geometric set cover and hitting set.  ACM Transactions on Algorithms (TALG), 18(4):1–37, 2022.
  * [2] Pankaj K Agarwal and Jiangwei Pan.  Near-linear algorithms for geometric hitting sets and set covers.  In Proceedings of the thirtieth Annual Symposium on Computational Seometry, pages 271–279, 2014.
  * [3] Boris Aronov, Esther Ezra, and Micha Shair.  Small-size $\varepsilon$-nets for axis-parallel rectangles and boxes.  In Proceedings of the forty-first annual ACM Symposium on Theory of Computing, pages 639–648, 2009.
  * [4] Therese Biedl, Ahmad Biniaz, and Anna Lubiw.  Minimum ply covering of points with disks and squares.  Comput. Geom., 94:101712, 2021.  doi:10.1016/j.comgeo.2020.101712.
  * [5] Hervé Brönnimann and Michael T Goodrich.  Almost optimal set covers in finite vc-dimension.  In Proceedings of the tenth Annual Symposium on Computational Geometry, pages 293–302, 1994.
  * [6] Timothy Chan and Qizheng He.  More dynamic data structures for geometric set cover with sublinear update time.  Journal of Computational Geometry, 13(2):90–114, 2022.
  * [7] Timothy M Chan and Qizheng He.  Faster approximation algorithms for geometric set cover.  arXiv preprint arXiv:2003.13420, 2020.
  * [8] Timothy M Chan, Qizheng He, Subhash Suri, and Jie Xue.  Dynamic geometric set cover, revisited.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3496–3528. SIAM, 2022.
  * [9] Kenneth L Clarkson and Kasturi Varadarajan.  Improved approximation algorithms for geometric set cover.  In Proceedings of the twenty-first Annual Symposium on Computational Geometry, pages 135–141, 2005.
  * [10] Stephane Durocher, J Mark Keil, and Debajyoti Mondal.  Minimum ply covering of points with unit squares.  In WALCOM: Algorithms and Computation: 17th International Conference and Workshops, WALCOM 2023, Hsinchu, Taiwan, March 22–24, 2023, Proceedings, pages 23–35. Springer, 2023.
  * [11] Thomas Erlebach and Erik Jan van Leeuwen.  Approximating geometric coverage problems.  In Shang-Hua Teng, editor, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, pages 1267–1276. SIAM, 2008\.  URL: http://dl.acm.org/citation.cfm?id=1347082.1347220.
  * [12] Arindam Khan, Aditya Lonkar, Saladi Rahul, Aditya Subramanian, and Andreas Wiese.  Online and dynamic algorithms for geometric set cover and hitting set.  In Proceedings of the thirty-ninth Annual Symposium on Computational Seometry, 2023.
  * [13] Fabian Kuhn, Pascal von Rickenbach, Roger Wattenhofer, Emo Welzl, and Aaron Zollinger.  Interference in cellular networks: The minimum membership set cover problem.  In Lusheng Wang, editor, Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-29, 2005, Proceedings, volume 3595 of Lecture Notes in Computer Science, pages 188–198. Springer, 2005.  doi:10.1007/11533719\\_21.
  * [14] Joseph SB Mitchell and Supantha Pandit.  Minimum membership covering and hitting.  Theoretical Computer Science, 876:1–11, 2021.
  * [15] Kasturi Varadarajan.  Weighted geometric set cover via quasi-uniform sampling.  In Proceedings of the forty-second ACM symposium on Theory of computing, pages 641–648, 2010.