# Minimum-Membership Geometric Set Cover, Revisited

Sayan Bandyapadhyay, William Lochet, Saket Saurabh, Jie Xue

► To cite this version:

Sayan Bandyapadhyay, William Lochet, Saket Saurabh, Jie Xue. Minimum-Membership Geometric Set Cover, Revisited. SoCG 2023 - 39th International Symposium on Computational Geometry, Jun 2023, Dallas, United States. pp.11:1-11:14, 10.4230/LIPIcs.SoCG.2023.11 . hal-04288117

HAL Id: hal-04288117

https://hal.science/hal-04288117v1

Submitted on 17 Nov 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Minimum-Membership Geometric Set Cover, Revisited

Sayan Bandyapadhyay ⒰

Portland State University, OR, USA

William Lochet ⒰

LIRMM, Université de Montpellier, CNRS, Montpellier, France

Saket Saurabh ⒰

Institute of Mathematical Sciences, Chennai, India

Jie Xue ⒰, ⒰

New York University Shanghai, China

## 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 $\text{memb}(S, \mathcal{R}^*)$, is minimized, where $\text{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(\text{opt})}$ where 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.

**2012 ACM Subject Classification** Theory of computation → Design and analysis of algorithms

**Keywords and phrases** geometric set cover, geometric optimization, approximation algorithms

**Digital Object Identifier** 10.4230/LIPIcs.SoCG.2023.11

**Related Version** Full Version: https://arxiv.org/abs/2305.03985

**Funding** Saket Saurabh: Supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 819416), and Swarnajayanti Fellowship (No. DST/SJF/MSA01/2017-18).

**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.

<figure><img src="image_2.png" /></figure>

© Sayan Bandyapadhyay, William Lochet, Saket Saurabh, and Jie Xue;

licensed under Creative Commons License CC-BY 4.0

39th International Symposium on Computational Geometry (SoCG 2023).

Editors: Erin W. Chambers and Joachim Gudmundsson; Article No. 11; pp. 11:1–11:14

Leibniz International Proceedings in Informatics

<figure><img src="image_3.png" /></figure>

LIPICS

Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

<figure><img src="image_4.png" /></figure>
1 Introduction

Geometric set cover is one of the most fundamental problems in computational geometry. In 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 applications, several variants of the geometric set cover problem have 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 $\text{memb}(S, \mathcal{R}^*)$, is minimized, where $\text{memb}(S, \mathcal{R}^*) = \max_{p \in S} |\{R \in \mathcal{R}^* : p \in R\}|$.

Kuhn et al. [7], 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 [6], 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(\text{opt})}$ where *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 (generalized MMGSC).** In the generalized minimum-membership geometric set cover (MMGSC) problem, the input consists of two sets $S, S'$ 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 $\text{memb}(S', \mathcal{R}^*)$ is minimized. We denote by $\text{opt}(S, S', \mathcal{R})$ the optimum of the problem instance $(S, S', \mathcal{R})$, i.e., $\text{opt}(S, S', \mathcal{R}) = \text{memb}(S', \mathcal{R}^*)$ where $\mathcal{R}^* \subseteq \mathcal{R}$ is an optimal solution.

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

As our second result, we gave 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 in polynomial time with a factor of $o(\log n)$, while the minimum-size
set cover problem with halfplanes can be solved in polynomial time. Again, our PTAS works
for the generalized version.

**► Theorem 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 [3] 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 $R^* \subseteq R$ to covers S such that the ply of $R^*$ is minimized, where the ply is defined as the maximum number of objects in $R^*$ which have a nonempty common intersection. Observe that MPGSC is a special case of the generalized MMGSC (by letting $S'$ include a point in every face of the arrangement induced by $R$). As such, Theorems 2 and 3 both apply to MPGSC.

Prior to our work, Biedl, Biniaz and Lubiw [3] 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 [5] 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 2 is already much more efficient than the one of [5] (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 $\tilde{O}(n)$ time; here $\tilde{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 4.** *The MPGSC problem with unit (or similarly sized) squares/disks admits constant-approximation algorithms with running time $\tilde{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 [8] 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. Due to the limited space, some (less important) proofs are omitted and can be found in the full version of the paper.

## 2 Constant approximation for unit squares

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

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

**Lemma 5.** Suppose that, for every $\square \in \Gamma$, $Q_{\square}^* \subseteq Q_{\square}$ is a $c$-approximation solution of the generalized MMGSC instance $(S_{\square}, S', Q_{\square})$. Then $\bigcup_{\square \in \Gamma} Q_{\square}^*$ is an $O(c)$-approximation solution of the instance $(S, S', Q)$.

**Proof.** First notice that $\bigcup_{\square \in \Gamma} Q_{\square}^*$ is a set cover of $S$, because any point $p \in S$ is contained in a grid cell $\square$ and thus $Q_{\square}^*$ covers $p$. Then we show that for any point $p' \in S'$, the number of unit squares in $\bigcup_{\square \in \Gamma} Q_{\square}^*$ containing $p'$ is at most $9c \cdot \text{opt}(S, S', Q)$. Suppose the grid cell containing $p'$ is $\square'$. Note that a unit square $Q \in \bigcup_{\square \in \Gamma} Q_{\square}^*$ contains $p'$ only if $Q \in Q_{\square}^*$ for a grid cell $\square$ that is either $\square'$ or one of the eight grid cells around $\square'$. For each such cell $\square$, the number of unit squares in $Q_{\square}^*$ containing $p'$ is at most $c \cdot \text{opt}(S_{\square}, S', Q_{\square})$, since $Q_{\square}^*$ is a $c$-approximation solution of $(S_{\square}, S', Q_{\square})$. It is clear that $\text{opt}(S_{\square}, S', Q_{\square}) \le \text{opt}(S, S', Q)$. Therefore, there can be at most $9c \cdot \text{opt}(S, S', Q)$ unit squares in $\bigcup_{\square \in \Gamma} Q_{\square}^*$ containing $p'$, which implies that $\bigcup_{\square \in \Gamma} Q_{\square}^*$ is a $9c$-approximation solution of $(S, S', Q)$. $\quad$

## 2.2 Partition the instance using LP

Based on the previous discussion, we will now assume that $S$ is contained in a grid cell $\square$ and all unit squares in $Q$ intersect $\square$. Note that the points in $S'$ can be everywhere in the plane. We shall formulate an LP relaxation of the generalized MMGSC instance $(S, S', 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 \ge 1$ for all $a \in A$. For another set $A'$ of points, we can define the membership of $A'$ with respect to this fractional set cover $\{x_B\}_{B \in \mathcal{B}}$ as $\text{memb}(A', \{x_B\}_{B \in \mathcal{B}}) = \max_{a' \in A'} \sum_{B \in \mathcal{B}, a' \in B} x_B$. The LP relaxation of the instance $(S, S', Q)$ simply asks for a fractional set cover of $S$ using the unit squares in $Q$ that minimizes the membership of $S'$ 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}{ll}
\min & y \\
\text{s.t.} & 0 \le x_Q \le 1 \quad \text{for all } Q \in \mathcal{Q}, \\
& \sum_{Q \in \mathcal{Q}, p \in Q} x_Q \ge 1 \quad \text{for all } p \in S, \\
& \sum_{Q \in \mathcal{Q}, p' \in Q} x_Q \le y \quad \text{for all } p' \in S'.
\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 6.** $y^* \le \text{opt}(S, S', Q)$.

**Proof.** Let $Q^* \subseteq Q$ be an optimal solution. We have $S \subseteq \bigcup_{Q \in \mathcal{Q}^*} \text{memb}(S', Q^*) = \text{opt}(S, S', Q)$. Set $x_Q = 1$ for $Q \in Q^*$, $X_Q = 0$ for $Q \notin Q^*$, and $y = \text{memb}(S', Q^*)$. These values satisfy the LP constraints. Therefore, $y^* \le y = \text{opt}(S, S', Q)$. $\quad$

Next, we shall partition the instance $(S, S', 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 $\square$ and all unit squares in $Q$ intersect $\square$. Let $c_1, c_2, c_3, c_4$ be the four corners of $\square$. We can partition $Q$ into
$Q_1, Q_2, Q_3, Q_4$, where $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 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 7.** For each $i \in \{1, 2, 3, 4\}$, we have $\sum_{Q \in Q_i, p \in Q} x_Q^* \ge \frac{1}{4}$ for all $p \in S_i$.

**Proof.** We have $\sum_{Q \in Q_i, p \in Q} x_Q^* = \delta_{p,i}$ and $\sum_{i=1}^4 \delta_{p,i} = \sum_{Q \in Q, p \in Q} x_Q^* \ge 1$, because of the LP constraints. Furthermore, $\delta_{p,i} \ge \delta_{p,j}$ for all $j \in \{1, 2, 3, 4\}$, as $p \in S_i$. Thus, $\delta_{p,i} \ge \frac{1}{4}$. ◀

We now partition the original instance into $(S_1, S', Q_1), \dots, (S_4, S', Q_4)$. Consider an index $i \in \{1, 2, 3, 4\}$. If we define $\tilde{x}_Q^* = 4x_Q^*$ for all $Q \in Q_i$, then the above fact implies $\sum_{Q \in Q_i, p \in Q} \tilde{x}_Q^* \ge 1$ for all $p \in S_i$. In other words, $\{\tilde{x}_Q^*\}_{Q \in Q_i}$ is a fractional set cover of $S_i$. Note that $\text{memb}(S', \{\tilde{x}_Q^*\}_{Q \in Q_i}) \le 4y^*$, because

$$4y^* \ge \sum_{Q \in Q, p' \in Q} 4x_Q^* \ge \sum_{Q \in Q_i, p' \in Q} \tilde{x}_Q^*$$

for all $p' \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', 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 = \cup_{i=1}^4 S_i$, the membership of $S'$ with respect to it is $O(y^*)$. A nice property of the instances $(S_i, S', Q_i)$ is that all unit squares in $Q_i$ contain the same corner $c_i$ of $\square$. 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', Q)$, where all points in $S$ lie in a grid cell $\square$ and all unit squares contain the same corner (say the bottom-left corner) of $\square$. 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 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 proof is omitted and can be found in the full paper). The second one gives a useful geometric property for unit squares containing the same corner of $\square$.

**Fact 8.** Let $S_0 \subseteq S$ be a subset and $Q_0 \subseteq Q$ be a minimum-size set cover of $S_0$. For any fractional set cover $\{\hat{x}_Q\}_{Q \in Q}$ of $S_0$, we have $\sum_{Q \in Q} \hat{x}_Q \ge |Q_0|$.

**Fact 9.** Let $Q^-, Q, Q^+$ be three unit squares all containing the bottom-left corner of $\square$ which satisfy $x(Q^-) \le x(Q) \le x(Q^+)$ and $y(Q^-) \ge y(Q) \ge y(Q^+)$. Then $Q^- \cap Q^+ \subseteq Q$.

**Proof.** Let $p \in Q^- \cap Q^+$. The fact $p \in Q^-$ implies $x(p) \le x(Q^-)$ and $y(Q^-) - 1 \le y(p)$. So we have $x(p) \le x(Q)$ and $y(Q) - 1 \le y(p)$. On the other hand, the fact $p \in Q^+$ implies $x(Q^+) - 1 \le x(p)$ and $y(p) \le y(Q^+)$. So we have $x(Q) - 1 \le x(p)$ and $y(p) \le y(Q)$. Therefore, $x(Q) - 1 \le x(p) \le x(Q)$ and $y(Q) - 1 \le y(p) \le y(Q)$, which implies that $p \in Q$. ◀

We say a unit square $Q \in Q$ is dominated by another unit square $Q' \in Q$ if $Q \cap \square \subseteq Q' \cap \square$. A unit square in $Q$ is maximal if it is not dominated by any other unit squares in $Q$. We denote by $Q_{max} \subseteq Q$ the set of maximal unit squares in $Q$. The following lemma shows that any minimum-size set cover of $S$ that only uses the unit squares in $Q_{max}$ is also a good approximation for the minimum-membership set cover.
<figure><img src="image_5.png" /><figcaption>Figure 1 Illustrating the rectangle R.</figcaption></figure>

**Lemma 10.** Let $Q^* \subseteq Q$ be a minimum-size set cover of $S$ such that $Q^* \subseteq Q_{\max}$, and $\{x_Q\}_{Q \in Q}$ be a fractional set cover of $S$. Then $\text{memb}(S', Q^*) \le \text{memb}(S', \{x_Q\}_{Q \in Q}) + 2$.

**Proof.** Suppose $Q^* = \{Q_1, \dots, Q_r\}$ where $x(Q_1) \le \dots \le x(Q_r)$. As $Q^* \subseteq Q_{\max}$, we must have $x(Q_1) < \dots < x(Q_r)$ and $y(Q_1) > \dots > y(Q_r)$. Consider a point $p' \in S'$. Let $i^- \in [r]$ (resp., $i^+ \in [r]$) be the smallest (resp., largest) index such that $p' \in Q_{i^-}$ (resp., $p' \in Q_{i^+}$). By Fact 9, we have $p' \in Q_{i^-} \cap Q_{i^+} \subseteq Q_i$ for all $i \in \{i^-, \dots, i^+\}$ and thus $|\{Q \in Q^* : p' \in Q\}| = i^+ - i^- + 1$. It suffices to show that $\sum_{Q \in Q, p' \in Q} x_Q \ge 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 $Q_0 = \{Q_{i-1}, \dots, Q_{i-1}, Q_{i+}, \dots, Q_r\}$. Observe that $Q_0$ covers $S_0$, since no unit square in $Q^* \setminus Q_0$ contains any point in $S_0$. We claim that $Q_0 \subseteq Q$ is a minimum-size set cover of $S_0$. Indeed, since $x(Q_{i-}) < \dots < x(Q_{i+})$ and $y(Q_{i-}) > \dots > y(Q_{i+})$, the points in $S \setminus 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 $Q'_0 \subseteq Q$ of $S_0$ such that $|Q'_0| < |Q_0|$, then $Q'_0$ together with $Q_1, \dots, Q_{i-}, Q_{i+}, \dots, Q_r$ form a set cover of $S$ whose size is smaller than $Q^*$, contradicting with the fact that $Q^*$ is a minimum-size set cover of $S$. Therefore, $Q_0 \subseteq Q$ is a minimum-size set cover of $S_0$. Now for each $Q \in Q$, define $\hat{x}_Q = x_Q$ if $Q \cap R \ne \emptyset$ and $\hat{x}_Q = 0$ if $Q \cap R = \emptyset$. As $\{x_Q\}_{Q \in Q}$ is a fractional set cover of $S$, for each $p \in S_0$, we have $\sum_{Q \in Q, p \in Q} x_Q \ge 1$, which implies $\sum_{Q \in Q, p \in Q} \hat{x}_Q \ge 1$ because $p \in R$ and thus $\hat{x}_Q = x_Q$ for all $Q \in Q$ such that $p \in Q$. So $\{\hat{x}_Q\}_{Q \in Q}$ is a fractional set cover of $S_0$. By Fact 8, we then have

$$ \sum_{Q \in Q} \hat{x}_Q \ge |Q_0| = i^+ - i^- - 1. \qquad (1) $$

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

$$ \sum_{Q \in Q, p' \in Q} x_Q \ge \sum_{Q \in Q, p' \in Q} \hat{x}_Q = \sum_{Q \in Q} \hat{x}_Q. \qquad (2) $$

Combining Equations 1 and 2, we have $\sum_{Q \in Q, p' \in Q} x_Q \ge i^+ - i^- - 1$. ◀

Using the above lemma, now it suffices to compute a minimum-size set cover of $S$ using the unit squares in $Q_{\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 $\text{memb}(S', \mathcal{Q}^*) \le \text{memb}(S', \{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', \mathcal{Q}_1)$, ..., $(S_4, S', \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 $\text{memb}(S', \{\tilde{x}_Q^*\}_{Q \in \mathcal{Q}_i}) \le 4y^* \le 4 \cdot \text{opt}(S, S', \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 $\text{memb}(S', \mathcal{Q}_i^*) \le \text{memb}(S', \{\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{aligned} \text{memb}(S', \mathcal{Q}^*) &\le \sum_{i=1}^4 \text{memb}(S', \mathcal{Q}_i^*) \\ &\le \sum_{i=1}^4 \text{memb}(S', \{\tilde{x}_Q^*\}_{Q \in \mathcal{Q}_i}) + 8 \\ &\le 16y^* + 8 \\ &\le 16 \cdot \text{opt}(S, S', \mathcal{Q}) + 8. \end{aligned} $$

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

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

# 3 Polynomial-time approximation scheme for halfplanes

Let $S, S'$ 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', \mathcal{H})$. Set $n = |S| + |S'| + |\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 \ge 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 $\text{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 $\text{ang}(H, J) = \text{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}\setminus\{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 \setminus \bigcup \mathcal{R}$, which is always a convex polygon (possibly unbounded). The following simple facts about halfplanes will be used throughout the section, and their proofs can be found in the full paper.

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

(i) For any halfplane $H \in \mathcal{R}$ and another halfplane $H'$ different from $H$, we have that $\bigcup \mathcal{R} \neq \bigcup \mathcal{R}'$, where $\mathcal{R}' = (\mathcal{R}\setminus\{H\}) \cup \{H'\}$.
11:8 Minimum-Membership Geometric Set Cover

(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 < \operatorname{ang}(H_1, H_2) < \operatorname{ang}(H_1, H_3) < \dots < \operatorname{ang}(H_1, H_t) < \pi$.

► **Fact 12.** Let $H_1, \dots, H_t$ be halfplanes such that $0 < \operatorname{ang}(H_1, H_2) < \operatorname{ang}(H_1, H_3) < \dots < \operatorname{ang}(H_1, H_t) \le \pi$. Then the following two properties hold.

(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\}$.

(ii) If {$H_1, \dots, H_t$} is irreducible, then $\bigcap_{i=1}^t H_i = H_1 \cap H_t$.

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

In this section, we show how to compute an (exact) optimal solution of the instance $(S, S', \mathcal{H})$
in $n^{O(\text{opt})}$ time. It suffices to solve a decision problem: given an integer $k \ge 0$, find a subset
$\mathcal{Z} \subseteq \mathcal{H}$ which covers $S$ and satisfies $\text{memb}(S', \mathcal{Z}) \le 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', \mathcal{H})$ in $n^{O(\text{opt})}$ time. In what follows, a valid
solution of $(S, S', \mathcal{H})$ refers to a subset $\mathcal{Z} \subseteq \mathcal{H}$ which covers $S$ and satisfies $\text{memb}(S', \mathcal{Z}) \le k$.

Let $\Delta$ be a sufficiently large number such that $S \cup S' \subseteq [-\Delta, \Delta]^2$. For convenience, we add to $\mathcal{H}$ four dummy halfplanes with equations $y \le -\Delta$, $y \ge \Delta$, $x \le -\Delta$, and $x \ge \Delta$. As these dummy halfplanes does not contain any points in $S \cup S'$, 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, whose proof can be found in the full paper.

► **Fact 13.** If $(S, S', \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$.

If $(S, S', \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', \mathcal{H})$. In what follows, we assume $(S, S', \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', \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', \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 $\Gamma$ is $\mathcal{H}$-compatible
if each edge $e$ of $\Gamma$ is a portion of the boundary line of some halfplane $H \in \mathcal{H}$ such that
$\Gamma \cap H = e$ (or equivalently $H$ does not contain $\Gamma$). Note that the complement region of a
regular valid solution is an $\mathcal{H}$-compatible convex polygon $\Gamma$ which satisfies (i) no point in
$S$ lies in the interior of $\Gamma$ and (ii) for any $k+1$ edges $e_1, \dots, e_{k+1}$ of $\Gamma$, the intersection
$\bigcap_{i=1}^{k+1} H(e_i)$ does not contain any point in $S'$; here $H(e) \in \mathcal{H}$ denotes the halfplane whose
boundary line containing $e$ and $\Gamma \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', \mathcal{H})$, which is just the set of halfplanes corresponding to the edges of $\Gamma$. With
this observation, it suffices to find an $\mathcal{H}$-compatible convex polygon $\Gamma$ satisfying the two conditions. We notice the following fact which can be used to simplify condition (ii).

**Fact 14.** If there exist $t$ edges $e_1, \dots, e_t$ of an $\mathcal{H}$-compatible convex polygon $\Gamma$ such that $(\bigcap_{i=1}^t H(e_i)) \cap S' \neq \emptyset$, then there exist $t$ consecutive edges $f_1, \dots, f_t$ of $\Gamma$ such that $(\bigcap_{i=1}^t H(f_i)) \cap S' \neq \emptyset$.

**Proof.** Set $\mathcal{R} = \{H(e_1), \dots, H(e_t)\}$ and assume $(\bigcap \mathcal{R}) \cap S' \neq \emptyset$, which implies $\bigcap \mathcal{R} \neq \emptyset$. Note that the set of halfplanes corresponding to the edges of $\Gamma$ are irreducible, because $\Gamma$ is $\mathcal{H}$-compatible and thus the interior of each edge $e$ of $\Gamma$ 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 11, there exist $e^-, e^+ \in \{e_1, \dots, e_t\}$ such that $\mathrm{ang}(H(e^-), H(e_i)) \le \mathrm{ang}(H(e^-), H(e^+)) < \pi$ for all $i \in [t]$. Now we go clockwise along the boundary of $\Gamma$ from $e^-$ to $e^+$, and let $E$ be the set of edges of $\Gamma$ we visit (including $e^-$ and $e^+$). Clearly, $e_i \in E$ for all $i \in [t]$ and thus $|E| \ge t$. Furthermore, $0 < \mathrm{ang}(H(e^-), H(e)) < \mathrm{ang}(H(e^-), H(e^+)) < \pi$ for all $e \in E \setminus \{e^-, e^+\}$. Define $\mathcal{R}' = \{H(e) : e \in E\}$. Since $\mathcal{R}$ and $\mathcal{R}'$ are both irreducible, we can apply (ii) of Fact 12 to deduce $\bigcap \mathcal{R} = H(e^-) \cap H(e^+) = \bigcap \mathcal{R}'$, which implies $(\bigcap \mathcal{R}') \cap S' \neq \emptyset$. Finally, because $E$ consists of consecutive edges of $\Gamma$ and $|E| \ge t$, there exist $f_1, \dots, f_t \in E$ which are $t$ consecutive edges of $\Gamma$. We have $\bigcap \mathcal{R}' \subseteq \bigcap_{i=1}^t H(f_i)$ and thus $(\bigcap_{i=1}^t H(f_i)) \cap S' \neq \emptyset$. $\quad \blacksquare$

By the above fact, we only need to find an $\mathcal{H}$-compatible convex polygon $\Gamma$ which satisfies (i) no point in $S$ lies in the interior of $\Gamma$ and (ii) $(\bigcap_{i=1}^{k+1} H(e_i)) \cap S' \neq \emptyset$ for any $k+1$ consecutive edges $e_1, \dots, e_{k+1}$ of $\Gamma$. For convenience, we say $\Gamma$ 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 $\Phi$ to denote the set of these segments. Note that $|\Phi| = O(n^3)$, as $\Phi$ 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 $\Phi$. Consider a segment $\phi \in \Phi$. 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 \Phi$, the two endpoints of $\phi$ and $p$ form a triangle $\Delta_{\phi}$. If $p \to a \to 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, $\mathrm{ang}(\vec{pa}, \vec{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 \Phi^{k+1}$ which satisfy the following three conditions.

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. $\mathrm{ang}(\overrightarrow{a_{i-1}a_i}, \overrightarrow{a_i a_{i+1}}) \le \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. $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' = \emptyset$.

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' = (\phi'_0, \phi'_1, \dots, \phi'_k)$ such that $(\phi_1, \dots, \phi_k) = (\phi'_0, \phi'_1, \dots, \phi'_{k-1})$, we add a directed edge from $v$ to $v'$ with weight $\mathrm{ang}(\vec{pa}, \vec{pb})$, where $a$ is
<figure><img src="image_6.png" /><figcaption>Figure 2 Illustrating the conditions for a vertex of G.</figcaption></figure>

the left endpoint of $\phi_0$ and $b$ is the left endpoint of $\phi'_0 = \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 \Phi$ and $p$ form a triangle $\Delta_{\phi}$. The key observation is the following lemma, whose proof (which is simple but tedious) can be found in the full paper.

**Lemma 15.** *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$.*

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 $Z \subseteq \mathcal{H}$ of $S$ satisfying $\mathrm{memb}(S', Z) \le 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(\mathrm{opt})}$ time.

## 3.2 An algorithm with constant additive error

In this section, we show how to compute in polynomial time an approximation solution $Z \subseteq \mathcal{H}$ of the instance $(S, S', \mathcal{H})$ with constant additive error, that is, $\mathrm{memb}(S', Z) = \mathrm{opt}(S, S', \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} \ne \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 $Z$ and $Z'$, we write $Z \prec Z'$ if $\bigcup Z \subseteq \bigcup Z'$, and $Z \preceq Z'$ if $\bigcup Z \subseteq \bigcup Z'$. We define the following notion of “locally (non-)improvable” solutions.

**Definition 16.** A subset $Z \subseteq \mathcal{H}$ is *k-*expandable if there exists $Z' \subseteq \mathcal{H}$ such that $|Z \setminus Z'| = |Z'| - k$ and $Z \prec Z'$. A subset of $\mathcal{H}$ is *k-*stable if it is not *k-*expandable.

In other words, $Z \subseteq \mathcal{H}$ is *k-*expandable (resp., *k*-stable) if we can (resp., cannot) replace *k* halfplanes in $Z$ with other *k* halfplanes in $\mathcal{H}$ to shrink the complement region of $Z$. We are interested in subsets $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 17.** *A minimum-size set cover $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}' \subseteq \mathcal{H}$ such that $|\mathcal{Z} \setminus \mathcal{Z}'| = |\mathcal{Z}' \setminus \mathcal{Z}| \le k$ and $\mathcal{Z} \prec \mathcal{Z}'$, we update $\mathcal{Z}$ to $\mathcal{Z}'$. 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 \ge 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} \ne \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}' \subseteq \mathcal{H}$ satisfying $|\mathcal{Z} \setminus \mathcal{Z}'| = |\mathcal{Z}' \setminus \mathcal{Z}| \le 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 18.** If $\mathcal{Z} \subseteq \mathcal{H}$ is a minimum-size set cover of $S$ that is 1-stable, then we have $|\mathcal{Z}| \le \text{opt}(S, S', \mathcal{H}) + 2$.

**Proof.** Consider a point $p \in S'$. We show that $\text{memb}(p, \mathcal{Z}') \ge \text{memb}(p, \mathcal{Z}) - 2$ for any set cover $\mathcal{Z}' \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) \ne \emptyset$, by (ii) of Fact 11 and the assumption $\bigcup \mathcal{H} \ne \mathbb{R}^2$, we have $\mathcal{Z}(p) = \{H_1, \dots, H_r\}$ such that $0 < \text{ang}(H_1, H_2) < \text{ang}(H_1, H_3) < \dots < \text{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 \subseteq \mathcal{Z}'$ consist of halfplanes that contain at least one point in $S_0$. Note that $|\mathcal{Z}'_0| \ge r - 2$, for otherwise $(\mathcal{Z} \setminus \{H_2, \dots, H_{r-1}\}) \cup \mathcal{Z}'_0$ 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$ contains $p$ and thus

$$ \text{memb}(p, \mathcal{Z}') \ge \text{memb}(p, \mathcal{Z}'_0) = |\mathcal{Z}'_0| \ge r - 2 = \text{memb}(p, \mathcal{Z}) - 2. $$

Consider a halfplane $H' \in \mathcal{Z}'_0$. We want to show $p \in H'$. By the construction of $\mathcal{Z}'_0$, $H'$ 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} \setminus \{H_2, \dots, H_{r-1}\}$. In particular, $q \notin H_1$ and $q \notin H_r$, which implies $H' \ne H_1$ and $H' \ne H_r$. We observe that $\{H_1, H_r, H'\}$ is irreducible. Clearly, $H'$ is not redundant in $\{H_1, H_r, H'\}$, 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'\}$, then $\mathcal{Z} \preceq (\mathcal{Z} \setminus \{H_1\}) \cup \{H'\}$. Since $\mathcal{Z}$ is irreducible and $H' \ne H_1$, by (i) of Fact 11, this implies $\mathcal{Z} \prec (\mathcal{Z} \setminus \{H_1\}) \cup \{H'\}$, which contradicts the fact
11:12 Minimum-Membership Geometric Set Cover

that $\mathcal{Z}$ is 1-stable. So $H_1$ is not redundant in $\{H_1, H_r, H'\}$. For the same reason, $H_r$ is also not redundant in $\{H_1, H_r, H'\}$. Thus, $\{H_1, H_r, H'\}$ is irreducible.

In what follows, we complete the proof by showing that either $p \in H'$ or $\mathcal{Z}$ is 1-expandable. As the latter is false (for $\mathcal{Z}$ is 1-stable), this implies $p \in H'$. If $\mathrm{ang}(H_1, H') < \mathrm{ang}(H_1, H_r)$, by the irreducibility of $\{H_1, H_r, H'\}$ and (ii) of Fact 12, we have $H_1 \cap H' \cap H_r = H_1 \cap H_r$, which implies $H_1 \cap H_r \subseteq H'$ and thus $p \in H_1 \cap H_r \subseteq H'$. If $\mathrm{ang}(H_1, H') = \mathrm{ang}(H_1, H_r)$, then either $H' \subseteq H_r$ or $H_r \subseteq H'$. Note that the former is not true as $q \in H'$ but $q \notin H_r$. Thus, we have $p \in H_r \subseteq H'$. It suffices to consider the case $\mathrm{ang}(H_1, H') > \mathrm{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 $\mathrm{ang}(H_1, H) < \mathrm{ang}(H_1, H_r) < \mathrm{ang}(H_1, H')$, which implies $\mathrm{ang}(H, H_r) < \mathrm{ang}(H, H')$ and $\mathrm{ang}(H', H_1) < \mathrm{ang}(H', H)$. We further distinguish two cases, $\mathrm{ang}(H, H') \le \pi$ and $\mathrm{ang}(H, H') \ge \pi$ (which are in fact symmetric). Assume $\mathrm{ang}(H, H') \le \pi$. Figure 3 shows the situation of the points $p, q$ and the halfplanes $H, H', H_1, H_r$ in this case. As $\mathrm{ang}(H, H_r) < \mathrm{ang}(H, H')$, by (ii) of Fact 12, if $\{H, H_r, H'\}$ is irreducible, then $H \cap H_r \cap H' = H \cap H'$. But $H \cap H_r \cap H' \ne H \cap H'$, because $q \in H \cap H'$ and $q \notin H_r$. Thus, $\{H, H_r, H'\}$ is reducible. Note that $H \cup H' \ne \mathbb{R}^2$, since $\cup \mathcal{H} \ne \mathbb{R}^2$ by our assumption. So by (i) of Fact 12, neither $H$ nor $H'$ is redundant in $\{H, H_r, H'\}$. It follows that $H_r$ is redundant in $\{H, H_r, H'\}$, because $\{H, H_r, H'\}$ is reducible. Therefore, $\mathcal{Z} \preceq (\mathcal{Z} \setminus \{H_r\}) \cup \{H'\}$. Since $\mathcal{Z}$ is irreducible and $H' \ne H_r$, by (i) of Fact 11, we have $\mathcal{Z} \prec (\mathcal{Z} \setminus \{H_r\}) \cup \{H'\}$, i.e., $\mathcal{Z}$ is 1-expandable. The other case $\mathrm{ang}(H, H') \ge \pi$ is similar. In this case, $\mathrm{ang}(H', H) \le \pi$. Using the fact $\mathrm{ang}(H', H_1) < \mathrm{ang}(H', H)$ and the same argument as above, we can show that $\mathcal{Z} \prec (\mathcal{Z} \setminus \{H_1\}) \cup \{H'\}$, i.e., $\mathcal{Z}$ is 1-expandable. $\quad$

<figure><img src="image_7.png" /><figcaption>■ **Figure 3** Illustration of the proof of Lemma 18.</figcaption></figure>

Using Lemma 17, 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 18, $\mathcal{Z}$ is an approximation solution for the MMGSC instance $(S, S', \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}| \ge \frac{1+\varepsilon}{\varepsilon} \cdot c$, then

$$ \frac{|\mathcal{Z}|}{\mathrm{opt}(S, S', \mathcal{H})} \le \frac{|\mathcal{Z}|}{|\mathcal{Z}| - c} \le 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 $\mathrm{opt}(S, S', \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.

**Theorem 3.** *The generalized MMGSC problem with halfplanes admits a PTAS.*

# 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 technique. We construct a grid $\Gamma$ consisting of square cells of side-length 1. For each grid cell $\square$, write $S_{\square} = S \cap \square$ and $\mathcal{Q}_{\square} = \{Q \in \mathcal{Q} : Q \cap \square \neq \emptyset\}$. The key observation is the following.

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

**Proof.** Let $\gamma = \mathrm{ply}(\bigcup_{\square \in \Gamma} \mathcal{Q}_{\square}^*)$ and $p \in \mathbb{R}^2$ be a point contained in $\gamma$ unit squares in $\bigcup_{\square \in \Gamma} \mathcal{Q}_{\square}^*$. Consider the grid cell $\square_p$ containing $p$ and define $\mathcal{C}$ as the set of $3 \times 3$ grid cells centered at $\square_p$. Note that all unit squares containing $p$ belong to $\bigcup_{\square \in \Gamma} \mathcal{Q}_{\square}^*$. So we have $|\bigcup_{\square \in \Gamma} \mathcal{Q}_{\square}^*| \ge \gamma$ and $|\max_{\square \in \Gamma} \mathcal{Q}_{\square}^*| \ge \gamma/9$. Therefore, there exists $\square \in \Gamma$ such that $|\mathcal{Q}_{\square}^*| \ge \gamma/9$. As $\mathcal{Q}_{\square}^*$ is a $c$-approximation solution of the minimum-size set cover instance $(S_{\square}, \mathcal{Q}_{\square})$, we know that any subset of $\mathcal{Q}_{\square}$ that covers $S_{\square}$ 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}_{\square}$. Note that each of these unit squares contains a corner of $\square$. Thus, at least one corner of $\square$ 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_{\square \in \Gamma} \mathcal{Q}_{\square}^*$ 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 20.** *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) \ge 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_{\square}, \mathcal{R}_{\square})\}$ 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}_{\square}^* \subseteq \mathcal{R}_{\square}$. By Lemma 19, $\bigcup_{\square \in \Gamma} \mathcal{R}_{\square}^*$ 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) \ge T(a)+T(b)$. ◀
11:14 Minimum-Membership Geometric Set Cover

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

*Proof.* The $\tilde{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, 4]. Applying Theorem 20 directly yields $\tilde{O}(n)$-time constant-approximation algorithms for MPGSC with unit squares and unit disks. ◀

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 geometry*, pages 271–279, 2014.

3. 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.

4. Timothy M Chan and Qizheng He. Faster approximation algorithms for geometric set cover. In *36th International Symposium on Computational Geometry (SoCG 2020)*, volume 164, page 27. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2020.

5. 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.

6. 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.

7. 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.

8. Joseph SB Mitchell and Supantha Pandit. Minimum membership covering and hitting. *Theoretical Computer Science*, 876:1–11, 2021.