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², 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)=maxp∈ P|∈ S: p∈ s\|. For unit squares, we present a simple O(nlog 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ᵈ⁻¹ times the size of a minimum-sized $1$-membership cover is computed in O(dnlog 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(nlog n + nm) time.