2023/05/06 by Bandyapadhyay, Sayan, Lochet, William, Saurabh, Saket +1 · 1 citation
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2305.03985
We revisit a natural variant of geometric set cover, called minimum-membership geometric set cover (MMGSC). In this problem, the input consists of a set S of points and a set R of geometric objects, and the goal is to find a subset R^*\subseteqR to cover all points in S such that the membership of S with respect to R^*, denoted by memb(S,R^*), is minimized, where memb(S,R^*)=maxp∈ S|\R\inR^*: p∈ R\|. 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 nO(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 R^*\subseteqR to cover 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. Very recently, Durocher et al. gave the first constant-approximation algorithm for MPGSC with unit squares which runs in O(n12) time. We give a significantly simpler constant-approximation algorithm with near-linear running time.