Seminars

View all Seminars  |  Download ICal for this event

Approximation and Hardness for Variants of Geometric Set Cover

Series: Ph.D. Colloquium

Speaker: Siddhartha Sarkar, Ph.D (Engg.) student, Dept. of CSA,

Date/Time: Jul 30 10:30:00

Location: CSA Auditorium, (Room No. 104, Ground Floor)

Faculty Advisor: Prof. Sathish Govindarajan

Abstract:
Geometric covering problems are fundamental in computational geometry and arise naturally in applications involving wireless sensing, communication, facility placement, and monitoring. In many such settings, minimizing only the number of selected objects is insufficient: excessive coverage overlap may cause interference or redundant load, while identical coverage patterns may prevent distinct locations from being identified. This thesis develops structural, approximation, and hardness results for geometric covering under these richer incidence constraints.

Building on these considerations, this thesis examines two complementary variants of Geometric Set Cover. The first is Minimum-Membership Geometric Set Cover, which controls the maximum number of selected objects containing any input point. The second is Geometric Discriminating Code, which requires distinct points to be covered by distinct sets of selected objects. Both directions are governed by the point--object incidence patterns induced by the selected geometric objects.

The first part of the thesis concerns Minimum-Membership Geometric Set Cover in the discrete and continuous setting. The membership of a point set $P$ with respect to a set cover $S^{*}$ of $P$ is the maximum number of objects in $S^{*}$ containing a point of $P$. Firstly, we study discrete generalized minimum-membership geometric set cover with axis-parallel unit squares. Here, the input consists of finite point sets $P$ and $P^{*}$ in $mathbb R^2$ and a finite family $S$ of unit squares. The objective is to select a subset $S^{*} subseteq S$ that covers $P$, while minimizing the membership of $P^{*}$ with respect to $S^{*}$. We develop a local-exchange algorithm for a special case of the problem called line instances and combine its structural properties with an LP-based slab decomposition. The resulting polynomial-time algorithm returns a cover of membership at most $16OPT+36$, improving the asymptotic approximation factor from $144$, due to Bandyapadhyay, Lochet, Saurabh, and Xue (SoCG 2023), to $16$.

We next consider Minimum-Membership Geometric Set Cover in the continuous setting. Here, the input consists of a finite set $P$ of points in $mathbb R^2$ and a geometric object $K$. The objective is to place translated copies of $K$ that cover $P$ while minimizing the membership of $P$. Our main geometric result proves that every finite point set $P$ in $mathbb R^2$ can be covered by translates of any fixed planar convex polygon such that the membership of $P$ is at most two, which is tight. This improves the previous universal bound of four for convex polygons, due to Govindarajan, Patle, and Sarkar (COCOON 2025). The proof uses affine-regular hexagon theorem of Fary, with a periodic tiling construction to obtain a tight two-membership cover.

To address cardinality, let $OPT_c(P,K)$ denote the minimum number of translates of a planar convex object $K$ required to cover $P$ with membership at most $c$. We develop a deterministic shifted-grid framework based on bounded local membership-coverability and finite incidence-preserving canonical families in translation space. For every fixed $varepsilon>0$, it yields a cover of membership at most eight and size at most $(1+varepsilon)OPT_2(P,K)$ for a fixed convex polygon and for unit disks. For axis-parallel unit squares, it gives a cover with membership at most four and size at most $(1+varepsilon)OPT_1(P,K)$. These guarantees strengthen earlier constant-factor cardinality bounds by obtaining cardinality arbitrarily close to the constrained low-membership optimum. We also prove that minimum-cardinality covering by unit disks remains NP-hard when the target membership is two.

The second part of the thesis concerns discrete geometric discriminating codes. In this problem, the input consists of a finite set $P$ of points and a finite set $S$ of geometric objects in $mathbb R^2$. A selected subset $S^{*} subseteq S$ assigns to each point $p in P$ a code defined as $code_{S^{*}}(p)={s in S^{*}:p in s}$. If every point in $P$ has a nonempty code and any two distinct points in $P$ have different codes, $S^{*}$ is said to discriminate $P$ and is called discriminating code. The objective is to minimize $|S^{*}|$.

Firstly, we study the discrete discriminating code problem for arbitrary intervals on the real line. We establish an exact cardinality-preserving equivalence with the unweighted Cycle Augmentation Problem. Combining this equivalence with the cycle augmentation algorithm of Galvez, Grandoni, Jabal Ameli, and Sornat (WAOA 2019) yields a polynomial-time $(1.5+ varepsilon)$-approximation for every fixed $varepsilon>0$, improving the factor-$2$ approximation of Dey, Foucaud, Nandy, and Sen (Algorithmica 2023). The equivalence also strengthens their NP-hardness result to APX-hardness.

We next consider the problem for axis-parallel unit squares. Dey, Foucaud, Nandy, and Sen (Algorithmica 2023) proved NP-hardness and obtained a solution-size bound of $64OPT+1$. We strengthen the hardness result to APX-hardness and improve the solution-size bound to $48OPT+1$. The improvement follows from an LP-relative factor-$3$ approximation for a line-stabbed rectangle-hitting subproblem.

Overall, this thesis establishes new structural results and algorithmic connections that yield improved approximation guarantees, tight low-membership bounds, and stronger hardness results for variants of Geometric Set Cover.