2025/05/30 by Sathish Govindarajan, Govindarajan, Sathish, Mayuresh Patle +3
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2506.00272
openalex publication_date 2025/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ℝ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)=maxp∈ P|\s∈ 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 2d-1 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.