2026-07-22T21:49:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17861 2024-03-06T11:00:33Z ddc:004 open_access

Minimum-Membership Geometric Set Cover, Revisited Bandyapadhyay, Sayan Lochet, William Saurabh, Saket Xue, Jie geometric set cover geometric optimization approximation algorithms 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 ℛ of geometric objects, and the goal is to find a subset ℛ^* ⊆ ℛ to cover all points in S such that the membership of S with respect to ℛ^*, denoted by memb(S,ℛ^*), is minimized, where memb(S,ℛ^*) = max_{p ∈ S} |{R ∈ ℛ^*: p ∈ R}|. We give the first polynomial-time approximation algorithms for MMGSC in ℝ². 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(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 ℛ^* ⊆ ℛ to cover S such that the ply of ℛ^* is minimized, where the ply is defined as the maximum number of objects in ℛ^* 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sayan Bandyapadhyay and William Lochet and Saket Saurabh and Jie Xue 2023 Is Part Of LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2023.11 urn:nbn:de:0030-drops-178610 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.11 eng https://creativecommons.org/licenses/by/4.0/legalcode