Abstract
We revisit a natural variant of the geometric set cover problem, called minimummembership 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 polynomialtime approximation algorithms for MMGSC in ℝ². Specifically, we achieve the following two main results.
 We give the first polynomialtime constantapproximation algorithm for MMGSC with unit squares. This answers a question left open since the work of Erlebach and Leeuwen [SODA'08], who gave a constantapproximation algorithm with running time n^{O(opt)} where opt is the optimum of the problem (i.e., the minimum membership).
 We give the first polynomialtime 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 wellknown that the minimumsize set cover problem with halfplanes can be solved in polynomial time. We also consider a problem closely related to MMGSC, called minimumply 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 constantapproximation algorithm for MPGSC with unit squares which runs in O(n^{12}) time. We give a significantly simpler constantapproximation algorithm with nearlinear running time.
BibTeX  Entry
@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2023.11,
author = {Bandyapadhyay, Sayan and Lochet, William and Saurabh, Saket and Xue, Jie},
title = {{MinimumMembership Geometric Set Cover, Revisited}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {11:111:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772730},
ISSN = {18688969},
year = {2023},
volume = {258},
editor = {Chambers, Erin W. and Gudmundsson, Joachim},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17861},
URN = {urn:nbn:de:0030drops178610},
doi = {10.4230/LIPIcs.SoCG.2023.11},
annote = {Keywords: geometric set cover, geometric optimization, approximation algorithms}
}
Keywords: 

geometric set cover, geometric optimization, approximation algorithms 
Collection: 

39th International Symposium on Computational Geometry (SoCG 2023) 
Issue Date: 

2023 
Date of publication: 

09.06.2023 