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 R^2, and a geometric object t, the goal is to find a set S of translated copies of the geometric object t that covers all the points in P while minimizing memb (P, S), where memb (P, S) =₏ ₏|\s S: p s\|. For unit squares, we present a simple O (n 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 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 n + nm) time.