Minimum Membership Geometric Set Cover in the Continuous Setting
摘要
We study the minimum membership geometric set cover, i.e., MMGSC problem [SoCG, 2023] in the continuous setting. In this problem, the input consists of a set P of n points in \(\mathbb {R}^{2}\) , and a geometric object t, the goal is to find a set \(\mathcal {S}\) of translated copies of the geometric object t that covers all the points in P while minimizing \(\textsf{memb}(P, \mathcal {S})\) , where \(\textsf{memb}(P, \mathcal {S})=\max _{p\in P}|\{s\in \mathcal {S}: p\in s\}|\) . For unit squares, we present a simple \(O(n\log n)\) time algorithm that outputs a 1-membership cover. We show that the size of our solution is at most twice that of an optimal solution. We establish the NP-hardness on the problem of computing the minimum number of non-overlapping unit squares required to cover a given set of points. This algorithm also generalizes to fixed-sized hyperboxes in d-dimensional space, where an 1-membership cover with size at most \(2^{d-1}\) times the size of a minimum-sized 1-membership cover is computed in \(O(dn\log n)\) time. Additionally, we characterize a class of objects for which a 1-membership cover always exists. For unit disks, we prove that a 2-membership cover exists for any point set, and the size of the cover is at most 7 times that of the optimal cover. For arbitrary convex polygons with m vertices, we present an algorithm that outputs a 4-membership cover in \(O(n\log n + nm)\) time.