Minimum Membership Geometric Set Cover in the Continuous Setting
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913868708577280 |
|---|---|
| author | Govindarajan, Sathish Patle, Mayuresh Sarkar, Siddhartha |
| author_facet | Govindarajan, Sathish Patle, Mayuresh Sarkar, Siddhartha |
| contents | 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 $\mathsf{memb}(P, \mathcal{S})$, where $\mathsf{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_00272 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Minimum Membership Geometric Set Cover in the Continuous Setting Govindarajan, Sathish Patle, Mayuresh Sarkar, Siddhartha Computational Geometry 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 $\mathsf{memb}(P, \mathcal{S})$, where $\mathsf{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. |
| title | Minimum Membership Geometric Set Cover in the Continuous Setting |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2506.00272 |